Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0until 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
1and1000nodes. - Each node in the linked list has
-1000 <= node.val <= 1000.
Solution: HashTable
Similar to target sum = 0, use a hashtable to store the first ListNode* that has a given prefix sum. Whenever the same prefix sum occurs, skip all the elements between the first occurrence and current one, e.g. first_sum_x.next = curr_sum_x.next
Time complexity: O(n)
Space complexity: O(n)
C++
|
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 |
// Author: Huahua class Solution { public: ListNode* removeZeroSumSublists(ListNode* head) { bool done = false; function<ListNode*(ListNode*)> helper = [&](ListNode* head) { ListNode dummy(0); dummy.next = head; ListNode* prev = &dummy; ListNode* curr = prev->next; unordered_map<int, ListNode*> m{{0, prev}}; int s = 0; done = true; while (curr) { s += curr->val; if (m.count(s)) { m[s]->next = curr->next; done = false; } else { m[s] = curr; } prev = curr; curr = curr->next; } return dummy.next; }; while (!done) head = helper(head); return head; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
# Author: Huahua class Solution: def removeZeroSumSublists(self, head: ListNode) -> ListNode: def helper(head: ListNode): dummy = ListNode(0) dummy.next = head prev, curr = dummy, dummy.next s = 0 m = {s: prev} done = True while curr: s += curr.val if s in m: m[s].next = curr.next done = False else: m[s] = curr prev, curr = curr, curr.next return dummy.next, done while True: head, done = helper(head) if done: return head |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment