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 public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode RemoveZeroSumSublists(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
bool removed = true;
while (removed) {
ListNode cur = dummy;
int sum = 0;
removed = false;
while (cur.next != null) {
sum += cur.next.val;
if (sum == 0) {
cur.next = cur.next.next;
removed = true;
} else {
cur = cur.next;
}
}
}
return dummy.next;
}
}The solution repeatedly scans the list, tracking sums, and bypasses nodes forming zero-sum sequences, continuing until no more can be found.