Scale Engineer

Remove Zero Sum Consecutive Nodes from Linked List

Med
#1099Time: O(N^2) - In the worst-case scenario (e.g., a list like `[1, 2, 3, ..., -sum]`), the outer loop runs N times, and for each, the inner loop might also run up to N times. This results in a quadratic time complexity.Space: O(1) - We only use a few pointers (`dummy`, `outer`, `inner`) to traverse the list, so the space used is constant regardless of the list size.2 companies
Data structures
Hash TableLinked List
Companies
ByteDancejosh technology

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a straightforward, brute-force method with nested loops to find and remove zero-sum consecutive subsequences. It iterates through all possible consecutive sublists, calculates their sum, and removes them if the sum is zero. This process is repeated until no such sublists can be found.

Algorithm

  1. Create a dummy node and set dummy.next = head. This simplifies handling cases where the head node is part of the sequence to be removed.
  2. Initialize an outer pointer to the dummy node.
  3. Loop with the outer pointer as long as it's not null.
  4. Inside this loop, start an inner loop with a pointer inner starting from outer.next and a sum initialized to 0.
  5. The inner loop traverses the rest of the list, accumulating the sum of node values.
  6. If at any point sum becomes 0, it means the consecutive sequence of nodes from outer.next to inner sums to zero.
  7. Upon finding such a sequence, we remove it by setting outer.next = inner.next. This effectively bypasses all the nodes in the zero-sum sequence.
  8. After a deletion, we break the inner loop and the outer loop continues from the same outer node, but with its next pointer updated. This is crucial because the deletion might have formed a new zero-sum sequence with earlier nodes.
  9. If the inner loop completes without the sum ever becoming 0, it means no zero-sum sequence starts at outer.next. In this case, we can safely advance outer to its next node.
  10. Finally, return dummy.next, which will be the head of the modified list.

Walkthrough

The brute-force approach systematically checks every possible consecutive sequence of nodes for a zero sum. We use a dummy node pointing to the head to handle deletions at the beginning of the list gracefully.

We iterate with an outer pointer, which marks the node just before the start of a potential zero-sum sequence. For each position of outer, we use an inner pointer to traverse the rest of the list, calculating the sum of nodes from outer.next to inner.

If the sum becomes zero, we've found a sequence to delete. We do this by updating the outer.next pointer to inner.next, effectively cutting the zero-sum sequence out of the list. After a deletion, we must re-evaluate from the same outer node, as the new connection might form another zero-sum sequence. If the inner loop finishes without finding a zero-sum sequence, we advance the outer pointer.

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode removeZeroSumSublists(ListNode head) {        ListNode dummy = new ListNode(0, head);        ListNode outer = dummy;         while (outer != null) {            int prefixSum = 0;            ListNode inner = outer.next;            boolean found = false;            while (inner != null) {                prefixSum += inner.val;                if (prefixSum == 0) {                    outer.next = inner.next;                    found = true;                    // Break inner loop and restart scan from the same outer node                    break;                 }                inner = inner.next;            }                        // Only advance outer if no deletion was made from its position            if (!found) {                outer = outer.next;            }            // If a deletion was made, outer stays put to re-check from its new .next        }         return dummy.next;    }}

Complexity

Time

O(N^2) - In the worst-case scenario (e.g., a list like `[1, 2, 3, ..., -sum]`), the outer loop runs N times, and for each, the inner loop might also run up to N times. This results in a quadratic time complexity.

Space

O(1) - We only use a few pointers (`dummy`, `outer`, `inner`) to traverse the list, so the space used is constant regardless of the list size.

Trade-offs

Pros

  • It's relatively easy to understand the logic.

  • It uses constant extra space, O(1), as it only requires a few pointers.

Cons

  • The time complexity of O(N^2) is inefficient for large linked lists and will be slow.

Solutions

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode removeZeroSumSublists ( ListNode head ) { ListNode dummy = new ListNode ( 0 , head ); Map < Integer , ListNode > last = new HashMap <>(); int s = 0 ; ListNode cur = dummy ; while ( cur != null ) { s += cur . val ; last . put ( s , cur ); cur = cur . next ; } s = 0 ; cur = dummy ; while ( cur != null ) { s += cur . val ; cur . next = last . get ( s ). next ; cur = cur . next ; } return dummy . next ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem