Merge Nodes Between Zeros — In-Place Pointer Walk Explained

Problem Statement#

LeetCode 2181 — Merge Nodes in Between Zeros Difficulty: Medium | Pattern: Pointer Walk + Accumulate

You are given the head of a linked list which contains a series of integers separated by zeros. The beginning and end of the linked list will have Node.val == 0. For every two consecutive zeros, merge all the nodes lying between them into a single node whose value is the sum of all merged nodes. The modified list should not contain any zeros.

Constraints:

• Number of nodes: 3 <= n <= 2 * 10^5
• 0 <= Node.val <= 1000
• The first and last node values are 0.
• There are no two consecutive zero-value nodes between the first and last zeros.

Example 1:

Input:  [0, 3, 1, 0, 4, 5, 2, 0]
Output: [4, 11]
Explanation:
  Segment [3, 1] between first pair of zeros → sum = 4
  Segment [4, 5, 2] between second pair of zeros → sum = 11

Example 2:

Input:  [0, 1, 0, 3, 0, 2, 2, 0]
Output: [1, 3, 4]

Why This Problem Matters#

This problem tests a clean and practical skill: accumulating values between delimiters in a sequence and producing a condensed output. The linked list format makes it slightly trickier than the array version because you cannot pre-allocate an output size — you must reuse existing nodes in-place.

The pattern of "accumulate until delimiter, then emit" appears in stream processing, log parsing, and data compression algorithms. In an interview at Amazon or during a LinkedIn phone screen, this type of simulation problem is used to test code clarity — can you write a clean, correct loop that handles the accumulation and resetting without introducing bugs?

What makes the in-place approach interesting is the node reuse trick: instead of allocating a new output list, you repurpose existing zero-value nodes as the containers for segment sums. This achieves O(1) extra space beyond the output, making the solution both time- and space-efficient.

The problem also has a conceptual connection to "Run-Length Encoding" — you are essentially compressing runs of values between delimiters into single summary nodes.

The Core Insight#

The key observation: the list always starts with a zero and ends with a zero. Every non-zero segment lies strictly between two zeros. You want to replace each such segment with a single node holding the segment sum.

In-place approach using node reuse:

1. Skip the leading zero. Let modify point to the dummy/first zero node where you will write sums.
2. Walk curr through the list. Accumulate non-zero values into total.
3. When you hit a zero (end of segment): write total into modify, advance modify to the current zero node, reset total = 0.
4. After the loop, terminate the list at modify.

This reuses the zero nodes as output nodes, which is O(1) space.

Alternative two-pointer approach: Maintain a write pointer and a read pointer. When read hits zero, update write.val = total and advance write. This is equivalent.

Visual Dry Run#

Input: [0, 3, 1, 0, 4, 5, 2, 0]

Output: modify.next = null → list is [4, 11].

Solution (Optimal)#

from typing import Optional
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def mergeNodes(head: Optional[ListNode]) -> Optional[ListNode]:
    # Skip the leading zero
    curr = head.next
    # modify points to the node where we write the next segment sum
    modify = head
 
    total = 0
    while curr:
        if curr.val != 0:
            total += curr.val
        else:
            # End of segment: write sum, advance modify, reset
            modify.val = total
            modify.next = curr  # tentatively point to this zero
            modify = modify.next
            total = 0
        curr = curr.next
 
    # Terminate the output list
    modify.next = None
 
    return head

function mergeNodes(head) {
    // Skip the leading zero
    let curr = head.next;
    let modify = head; // output write pointer
 
    let total = 0;
    while (curr !== null) {
        if (curr.val !== 0) {
            total += curr.val;
        } else {
            // End of segment: commit sum, advance modify, reset
            modify.val = total;
            modify.next = curr;
            modify = modify.next;
            total = 0;
        }
        curr = curr.next;
    }
 
    // The last modify points to the final zero — terminate there
    modify.next = null;
 
    return head;
}

Complexity:

Common Mistakes#

1. Not skipping the leading zero: The list always starts with a zero delimiter. Start traversal from head.next to avoid counting the leading zero as part of a segment.
2. Forgetting to terminate the output list: After the loop, modify.next may still point to old nodes. Always set modify.next = null to properly terminate.
3. Writing sum before advancing modify: The node reuse pattern requires writing to modify.val and then advancing modify to the current zero node. Mixing up this order corrupts the output.
4. Handling the trailing zero incorrectly: The trailing zero is the last delimiter. When you hit it, write the last sum and advance modify — then the loop ends. Setting modify.next = null terminates the output.
5. Mutating head.val: Since modify starts at head, you are overwriting head.val from 0 to the first segment sum. This is intended — the function returns head which now holds the first sum.

Interview Tips#

• Explain node reuse: "Instead of allocating a new list, I reuse the zero nodes as output containers. This gives O(1) extra space."
• Walk through the loop invariant: "At every point, modify points to the last output node written. When I hit a zero, I write total to modify.val, advance modify, and reset total."
• Mention the termination: Always talk about the final modify.next = null. Forgetting this is a common bug that leads to garbage tail nodes in the output.
• Offer the array alternative: "A simpler O(n) space approach collects sums in an array and builds a new list. I'll use the in-place approach for O(1) space."
• Test with example 2: The input [0, 1, 0, 3, 0, 2, 2, 0] has three segments. Walk through it to verify your solution produces [1, 3, 4].

Follow-up Questions#

1. What if zeros could appear consecutively (meaning empty segments)? Empty segments have sum 0 — you would need to decide whether to include zero-sum nodes or skip them.
2. What if the list did not start and end with zeros? You would need sentinel handling. The problem's guarantee of leading and trailing zeros simplifies the logic significantly.
3. What if you needed to preserve the original list? Allocate new nodes for each sum rather than reusing existing ones.
4. Can you solve it recursively? Yes — process the current segment, recurse for the rest. Space is O(n/k) where k is the average segment length due to the call stack.
5. LeetCode 2487 — Remove Nodes From Linked List: A related problem where you filter nodes based on conditions, also using in-place pointer manipulation.

Key Takeaways#

• The node reuse technique repurposes existing zero nodes as output containers, achieving O(1) extra space.
• Walk from head.next to skip the leading zero delimiter. Accumulate non-zero values into total.
• When you encounter a zero (segment boundary), write total into modify.val, advance modify to the current zero, and reset total.
• Always terminate the output list with modify.next = null after the loop to avoid garbage tail nodes.
• This problem's pattern — "accumulate between delimiters, emit summary node" — appears in stream processing, log parsing, and compression algorithms.
• Time is O(n) for a single pass; space is O(1) with node reuse, or O(n) with a fresh output list.