How to Remove Zero Sum Consecutive Nodes from Linked List using
- 时间:2020-09-10 13:03:17
- 分类:网络文摘
- 阅读:93 次
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) —
推荐阅读:诗酒永相随(文/白水先生) 学习古人的智慧 关于清明节的小作文200字 地震中的父与子500字 二年级作文家乡的水 都是马虎惹得祸作文200字 美味在眼前,我手煮我心 离殇 数学题:若用a型箱,正好要装800箱 数学题:神舟五号飞行轨道的近地点高度为200km
- 评论列表
-
- 添加评论