How to Remove Zero Sum Consecutive Nodes from Linked List using
- 时间:2020-09-10 13:03:17
- 分类:网络文摘
- 阅读:86 次
Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences. After doing so, return the head of the final linked list. You may return any such answer.
(Note that in the examples below, all sequences are serializations of ListNode objects.)
Example 1:
Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.Example 2:
Input: head = [1,2,3,-3,4]
Output: [1,2,4]Example 3:
Input: head = [1,2,3,-3,-2]
Output: [1]Constraints:
The given linked list will contain between 1 and 1000 nodes.
Each node in the linked list has -1000 <= node.val <= 1000.Hints:
Convert the linked list into an array.
While you can find a non-empty subarray with sum = 0, erase it.
Convert the array into a linked list.
Remove Zero-Sum Link Node usig Prefix/Cumulative Sum
The prefix sum can be stored and retrieved using a hash map. We accumulate the sum (as key), and store its node as value in the hash map. Then, when a sum occurs, we know the interval between two link nodes sum to zero. We can then re-point the previous node’s next to the next node which effectively removes the nodes between.
At the meantime, if the Cumulative sum from the begining is zero, we need to reset the head and recursively remove the zero sum lists.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* removeZeroSumSublists(ListNode* head) { ListNode* newHead = head; unordered_map<int, ListNode*> prefix; int sum = 0; bool flag = false; while (head) { sum += head->val; if (sum == 0) { newHead = head->next; flag = true; break; } else if (prefix.find(sum) == prefix.end()) { prefix[sum] = head; } else { prefix[sum]->next = head->next; flag = true; } head = head->next; } if (flag) { return removeZeroSumSublists(newHead); } return newHead; } }; |
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* removeZeroSumSublists(ListNode* head) { ListNode* newHead = head; unordered_map<int, ListNode*> prefix; int sum = 0; bool flag = false; while (head) { sum += head->val; if (sum == 0) { newHead = head->next; flag = true; break; } else if (prefix.find(sum) == prefix.end()) { prefix[sum] = head; } else { prefix[sum]->next = head->next; flag = true; } head = head->next; } if (flag) { return removeZeroSumSublists(newHead); } return newHead; } };
The above C++ code to remove the zero sum nodes for a given linked list runs at O(N) time and require O(N) space – using a hash map.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:如何吃辣椒不上火?怎样吃辣椒更健康? 冬季养生黄金期可多吃这些保健食物 三种食物滋阴润燥蜂蜜是冬天补养佳品 川贝雪梨适合秋咳 甘草片止咳不治咳 花生营养丰富怎么吃对人体健康最有益 吃水果的禁忌以及富含维生素的水果 黄瓜的营养价值保健效果及食用方法 土鸡蛋与洋鸡蛋的营养价值以及区别 冬季适当吃糯米类食物有御寒滋补之功效 三类护耳食物可以延缓老年人听力下降
- 评论列表
-
- 添加评论