How to Remove Zero Sum Consecutive Nodes from Linked List using
- 时间:2020-09-10 13:03:17
- 分类:网络文摘
- 阅读:97 次
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) —
推荐阅读:The Story Of Aaron Swartz And How His Death Could Change Compute Smart Finance Tips for Bloggers 8 Ways to Build Up Seed Money to Turn Your Blog into a Business Apple Reveals ARKit At WWDC Blogging From the Road: Japan Edition How to Redesign Your Blog for Improved User Experience Yes, It’s Possible to Grab Loans When Working as a Freelancer 2017 Most Unique and Friendliest CMS for Small Businesses 5 Easy Steps to Writing the Perfect Guest Post A Compilation of the Best Content Creation Strategies from 43 Ex
- 评论列表
-
- 添加评论