Problem Description

You are given a linked list that starts and ends with nodes having value 0. The list contains groups of non-zero integers separated by 0s.

Your task is to merge each group of non-zero values between consecutive 0s into a single node. The value of this new node should be the sum of all the non-zero values in that group. The resulting linked list should not contain any 0s.

For example, if you have a linked list like: 0 → 3 → 1 → 0 → 4 → 5 → 2 → 0, the output should be: 4 → 11

• The first group between zeros is [3, 1], which sums to 4
• The second group between zeros is [4, 5, 2], which sums to 11

The algorithm works by:

1. Starting from the node after the first 0 (since we know the list starts with 0)
2. Accumulating the sum of values until we encounter another 0
3. When we hit a 0, we create a new node with the accumulated sum and reset the sum to 0
4. We continue this process until we reach the end of the list
5. The dummy node technique is used to simplify handling the head of the result list

The time complexity is O(n) where n is the number of nodes in the original list, and the space complexity is O(1) excluding the output list.

Intuition

The key insight is recognizing that 0s act as delimiters that divide the linked list into segments. Since we need to merge all nodes between consecutive 0s, we can think of this as a "group and sum" problem.

When traversing a linked list, we naturally process nodes one by one. As we encounter non-zero values, we can accumulate them into a running sum. The moment we hit a 0, we know we've reached the end of a group - this is our signal to create a new node with the accumulated sum and reset our accumulator for the next group.

The pattern becomes clear: we're essentially in one of two states as we traverse:

1. Accumulating state: When we see non-zero values, add them to our sum
2. Creating state: When we see a 0, create a new node with the current sum and reset

Since the list starts with a 0, we can skip it and begin processing from the second node. Similarly, since it ends with a 0, our last accumulated sum will naturally be added when we encounter that final 0.

The use of a dummy node is a common linked list technique that eliminates special handling for the head of the result list. Instead of checking whether we're creating the first node or a subsequent node, we can uniformly append all new nodes to tail.next and return dummy.next at the end.

This approach emerges naturally when we think about the problem sequentially - process each element, accumulate when needed, and output when we reach a boundary marker (the 0s).

Learn more about Linked List patterns.

Solution Approach

We implement the solution using a single-pass traversal with the following components:

Data Structures:

• dummy: A dummy head node that simplifies list construction
• tail: A pointer that tracks where to append the next merged node
• s: An accumulator variable to store the running sum
• cur: A pointer to traverse the original linked list

Algorithm Steps:

1. Initialize the tracking variables:

   dummy = tail = ListNode()
   s = 0
   cur = head.next  # Skip the first 0

   We create a dummy node and set tail to point to it. Start traversal from head.next since we know the first node is always 0.

2. Traverse and process each node:

   while cur:
       if cur.val:
           s += cur.val
       else:
           tail.next = ListNode(s)
           tail = tail.next
           s = 0
       cur = cur.next

   For each node in the list:

   • If the value is non-zero (cur.val is truthy), add it to our accumulator s
   • If the value is 0, we've reached the end of a segment:
     • Create a new node with value s
     • Attach it to the result list via tail.next
     • Move tail forward to this new node
     • Reset s to 0 for the next segment
   • Move to the next node with cur = cur.next

3. Return the result:

   return dummy.next

   Since dummy is a placeholder, the actual result list starts at dummy.next.

Why this works:

• Every segment between 0s gets accumulated into s
• When we hit a 0, we know the segment is complete and create the merged node
• The dummy node pattern ensures we don't need special logic for the first merged node
• Since the list ends with 0, the last segment is automatically handled when we encounter the final 0

The time complexity is O(n) where n is the number of nodes, as we visit each node exactly once. The space complexity is O(1) for the auxiliary variables (not counting the output list).

Example Walkthrough

Let's trace through a small example: 0 → 2 → 3 → 0 → 5 → 0

Initial Setup:

• Create dummy and tail pointing to a new ListNode
• Set s = 0 (accumulator for sum)
• Set cur = head.next (pointing to node with value 2, skipping the first 0)
• Result list so far: dummy →

Step 1: Process node with value 2

• cur.val = 2 (non-zero)
• Add to sum: s = 0 + 2 = 2
• Move forward: cur now points to node with value 3
• Result list unchanged: dummy →

Step 2: Process node with value 3

• cur.val = 3 (non-zero)
• Add to sum: s = 2 + 3 = 5
• Move forward: cur now points to node with value 0
• Result list unchanged: dummy →

Step 3: Process node with value 0

• cur.val = 0 (delimiter found!)
• Create new node with accumulated sum: ListNode(5)
• Attach to result: tail.next = ListNode(5)
• Move tail forward: tail now points to the new node
• Reset sum: s = 0
• Move forward: cur now points to node with value 5
• Result list now: dummy → 5 →

Step 4: Process node with value 5

• cur.val = 5 (non-zero)
• Add to sum: s = 0 + 5 = 5
• Move forward: cur now points to final node with value 0
• Result list unchanged: dummy → 5 →

Step 5: Process final node with value 0

• cur.val = 0 (delimiter found!)
• Create new node with accumulated sum: ListNode(5)
• Attach to result: tail.next = ListNode(5)
• Move tail forward: tail now points to the new node
• Reset sum: s = 0
• Move forward: cur becomes None (end of list)
• Result list now: dummy → 5 → 5 →

Step 6: Return result

• Return dummy.next, which points to the first real node
• Final output: 5 → 5

The algorithm successfully merged [2, 3] into 5 and [5] into 5, removing all zeros from the original list.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the total number of nodes in the input linked list.

The algorithm traverses the entire linked list exactly once using a single while loop. For each node in the original list, we perform constant time operations:

• Checking if cur.val is non-zero: O(1)
• Adding to sum s: O(1)
• Creating a new node when encountering a zero: O(1)
• Moving the pointer cur forward: O(1)

Since we visit each of the n nodes exactly once and perform O(1) operations per node, the overall time complexity is O(n).

Space Complexity: O(m), where m is the number of segments (or the number of zeros minus one) in the input linked list.

However, since in the worst case m can be proportional to n (when zeros and non-zeros alternate), the space complexity can also be expressed as O(n).

The space is used for:

• Creating new ListNode objects for the result linked list. The number of new nodes created equals the number of segments between zeros.
• A few constant space variables (dummy, tail, s, cur): O(1)

The algorithm does not use recursion or any additional data structures that scale with input size beyond the output linked list itself, so the space complexity is determined by the size of the output, which is O(n) in the worst case.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Skip the Initial Zero

A common mistake is starting the traversal from head instead of head.next. Since the problem guarantees the list starts with 0, we must skip it to avoid processing it as part of the first group.

Incorrect:

current = head  # Wrong! This includes the first 0
while current:
    if current.val != 0:
        current_sum += current.val
    # ...

Correct:

current = head.next  # Skip the first 0
while current:
    if current.val != 0:
        current_sum += current.val
    # ...

2. Creating Empty Nodes for Consecutive Zeros

If the input contains consecutive zeros (like 0 → 3 → 0 → 0 → 5 → 0), you might accidentally create nodes with value 0 in the result, which violates the requirement that the output should not contain any zeros.

Solution: Add a check before creating a new node:

if current.val == 0:
    if current_sum > 0:  # Only create node if we have accumulated values
        tail.next = ListNode(current_sum)
        tail = tail.next
    current_sum = 0

3. Not Handling Edge Cases

The code might fail on edge cases like:

• A list with only zeros: 0 → 0 → 0
• A list with a single group: 0 → 5 → 0

Solution: The current implementation handles these correctly, but always test with:

# Test edge cases
# Input: 0 → 0 → 0 → 0
# Expected Output: None or empty list

# Input: 0 → 5 → 0
# Expected Output: 5

4. Memory Management with the Dummy Node

Forgetting to return dummy.next instead of dummy itself. The dummy node is just a placeholder and should not be part of the final result.

Incorrect:

return dummy_head  # Wrong! This includes the dummy node with value 0

Correct:

return dummy_head.next  # Correct! Skip the dummy node