Sponsored
Sponsored
This approach uses a hashmap to record prefix sums while iterating through the linked list. When a prefix sum is repeated, it indicates that the nodes between the occurrences of the prefix sum form a zero-sum sequence.
Time Complexity: O(n) where n is the number of nodes. Each node is visited at most twice.
Space Complexity: O(n) for the hashmap storing prefix sums.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def removeZeroSumSublists(self, head: ListNode) -> ListNode:
8 dummy = ListNode(0)
9 dummy.next = head
10 prefix_sum_map = {}
11 prefix_sum = 0
12 cur = dummy
13 while cur:
14 prefix_sum += cur.val
15 if prefix_sum in prefix_sum_map:
16 prev = prefix_sum_map[prefix_sum]
17 node = prev.next
18 p = prefix_sum
19 while node != cur:
20 p += node.val
21 del prefix_sum_map[p]
22 node = node.next
23 prev.next = cur.next
24 else:
25 prefix_sum_map[prefix_sum] = cur
26 cur = cur.next
27 return dummy.nextIn the Python solution, similar to others, a hashmap and a dummy node are used. The main loop calculates prefix sums and uses them to remove zero-sum subsequences.
This approach keeps processing the list until no zero-sum sublists can be found. This involves iterative rescanning of the list and skipping nodes accordingly.
Time Complexity: O(n^2) worst case, due to repeated scanning of the list.
Space Complexity: O(1), only a few local variables.
1
This JavaScript iteration continuously tracks and removes zero-sum sublists, ensuring thorough processing until no changes in the list occur.