LeetCode 2181 - Merge Nodes in Between Zeros

Difficulty: 🟡 Medium
Topics: Linked List, Simulation

Solution

Problem Understanding

The problem gives us a singly linked list where the values are grouped between 0 nodes. The list always starts with 0 and ends with 0, and there are no two consecutive zeros. Every sequence of non-zero nodes between two zeros represents one group.

Our task is to replace each group with a single node whose value equals the sum of all values in that group. The resulting linked list should contain only these summed nodes, with all zero nodes removed.

For example, consider the list:

0 -> 3 -> 1 -> 0 -> 4 -> 5 -> 2 -> 0

The first group lies between the first and second zero:

3 + 1 = 4

The second group lies between the second and third zero:

4 + 5 + 2 = 11

So the final linked list becomes:

4 -> 11

The constraints are important because the list may contain up to 2 * 10^5 nodes. This means we need a solution that processes the list efficiently in linear time. Any solution that repeatedly traverses portions of the list or performs expensive copying operations could become too slow.

The problem also provides several guarantees that simplify the implementation:

The list always starts with 0
The list always ends with 0
There are no consecutive zeros
Every group contains at least one non-zero value

These guarantees mean we never need to handle empty groups, and every time we encounter a zero after accumulating values, we know we have completed one valid segment.

Some important edge cases include:

A list containing only one group
Groups containing a single value
Very large lists with many groups
Groups with large sums
Consecutive small segments that could expose pointer mistakes in linked list manipulation

A naive implementation can easily make mistakes by incorrectly reconnecting nodes or accidentally including the boundary zeros in the sums.

Approaches

Brute Force Approach

A straightforward approach is to first extract all values from the linked list into an array. Once we have the array representation, we can iterate through it and compute the sum between zeros. After generating all sums, we can build a brand new linked list containing those values.

This works because arrays are easier to process than linked lists. We can sequentially scan the values and identify group boundaries whenever we encounter a zero.

However, this approach is not optimal because it requires extra memory proportional to the size of the list. We store all node values in an auxiliary array and then allocate another linked list for the answer.

Although the time complexity is still linear, the additional memory usage is unnecessary because the problem can be solved directly while traversing the original linked list.

Optimal Approach

The key observation is that we only need one running sum while traversing the linked list. Every time we encounter a 0, we know the current segment has ended, and we can append the accumulated sum as a new node in the result list.

Instead of converting the list into another data structure, we process the nodes in a single pass.

We maintain:

A running sum for the current segment
A pointer for building the result list
A traversal pointer for scanning the input list

Whenever we encounter a non-zero value, we add it to the running sum. Whenever we encounter a zero after processing a segment, we create a new node containing the accumulated sum and reset the running sum for the next segment.

This approach is efficient because every node is visited exactly once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Convert linked list to array, compute sums, rebuild list
Optimal	O(n)	O(1) auxiliary space	Single traversal with running segment sum

Algorithm Walkthrough

Start traversal from the node immediately after the initial zero because the first node is guaranteed to be 0 and does not contribute to any sum.
Create a dummy node for the result linked list. Using a dummy node simplifies appending new nodes because we do not need special handling for the first result node.
Maintain a variable called current_sum, initialized to 0. This variable stores the running sum of values between two zeros.
Traverse the linked list one node at a time.
If the current node contains a non-zero value, add it to current_sum. This means we are still inside the current segment.
If the current node contains 0, it means the current segment has ended. Create a new node with value current_sum and append it to the result list.
Reset current_sum back to 0 because the next segment begins after this zero.
Continue traversing until the end of the linked list is reached.
Return dummy.next, which points to the actual head of the merged result list.

Why it works

The algorithm maintains the invariant that current_sum always equals the sum of all non-zero nodes encountered since the most recent zero. Whenever another zero appears, the complete segment has been processed, so the accumulated sum is correct and can safely be appended to the result list. Since every node belongs to exactly one segment and every segment ends with a zero, all groups are processed exactly once.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        tail = dummy

        current = head.next
        current_sum = 0

        while current:
            if current.val == 0:
                tail.next = ListNode(current_sum)
                tail = tail.next
                current_sum = 0
            else:
                current_sum += current.val

            current = current.next

        return dummy.next

The implementation begins by creating a dummy node that serves as the starting point of the result list. This avoids special handling for the first insertion.

The traversal starts at head.next because the first node is always zero and does not belong to any segment.

The variable current_sum stores the cumulative sum of the current segment. During traversal:

Non-zero nodes contribute to the running sum
Zero nodes mark the end of a segment

Whenever a zero is encountered, a new node containing the accumulated sum is appended to the result list. The running sum is then reset for the next segment.

Finally, the method returns dummy.next, which skips the dummy node and points directly to the first merged node.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeNodes(head *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy

    current := head.Next
    currentSum := 0

    for current != nil {
        if current.Val == 0 {
            tail.Next = &ListNode{Val: currentSum}
            tail = tail.Next
            currentSum = 0
        } else {
            currentSum += current.Val
        }

        current = current.Next
    }

    return dummy.Next
}

The Go implementation follows the same logic as the Python version. The primary differences come from Go's explicit pointer handling and struct syntax.

In Go:

nil is used instead of None
New nodes are created using &ListNode{}
Struct fields are accessed using capitalized names like Val and Next

The algorithm still performs a single traversal while maintaining a running segment sum.

Worked Examples

Example 1

Input:

0 -> 3 -> 1 -> 0 -> 4 -> 5 -> 2 -> 0

Initial state:

Current Node	current_sum	Result List
3	0	empty

Process node 3:

Current Node	current_sum	Result List
3	3	empty

Process node 1:

Current Node	current_sum	Result List
1	4	empty

Process node 0:

Segment ends, append 4.

Current Node	current_sum	Result List
0	0	4

Process node 4:

Current Node	current_sum	Result List
4	4	4

Process node 5:

Current Node	current_sum	Result List
5	9	4

Process node 2:

Current Node	current_sum	Result List
2	11	4

Process final 0:

Append 11.

Current Node	current_sum	Result List
0	0	4 -> 11

Final output:

4 -> 11

Example 2

Input:

0 -> 1 -> 0 -> 3 -> 0 -> 2 -> 2 -> 0

Current Node	current_sum	Result List
1	1	empty
0	0	1
3	3	1
0	0	1 -> 3
2	2	1 -> 3
2	4	1 -> 3
0	0	1 -> 3 -> 4

Final output:

1 -> 3 -> 4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(1) auxiliary space	Only a few pointers and variables are used

The algorithm performs a single linear traversal of the linked list. No nested loops or repeated scans occur, so the runtime is proportional to the number of nodes.

The auxiliary space usage is constant because the algorithm only maintains a few variables and pointers. The output linked list itself is not counted toward auxiliary space complexity.

Test Cases

# Helper functions for testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    tail = dummy

    for value in values:
        tail.next = ListNode(value)
        tail = tail.next

    return dummy.next

def linked_list_to_list(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

class Solution:
    def mergeNodes(self, head):
        dummy = ListNode(0)
        tail = dummy

        current = head.next
        current_sum = 0

        while current:
            if current.val == 0:
                tail.next = ListNode(current_sum)
                tail = tail.next
                current_sum = 0
            else:
                current_sum += current.val

            current = current.next

        return dummy.next

solution = Solution()

# Example 1
head = build_list([0, 3, 1, 0, 4, 5, 2, 0])
assert linked_list_to_list(solution.mergeNodes(head)) == [4, 11]  # multiple groups

# Example 2
head = build_list([0, 1, 0, 3, 0, 2, 2, 0])
assert linked_list_to_list(solution.mergeNodes(head)) == [1, 3, 4]  # mixed segment sizes

# Single segment
head = build_list([0, 5, 5, 0])
assert linked_list_to_list(solution.mergeNodes(head)) == [10]  # one merged node

# Single values between zeros
head = build_list([0, 1, 0, 2, 0, 3, 0])
assert linked_list_to_list(solution.mergeNodes(head)) == [1, 2, 3]  # each segment has one value

# Large values
head = build_list([0, 1000, 1000, 1000, 0])
assert linked_list_to_list(solution.mergeNodes(head)) == [3000]  # large segment sum

# Many small segments
head = build_list([0, 1, 0, 1, 0, 1, 0, 1, 0])
assert linked_list_to_list(solution.mergeNodes(head)) == [1, 1, 1, 1]  # repeated short segments

Test	Why
`[0,3,1,0,4,5,2,0]`	Validates standard multi-group behavior
`[0,1,0,3,0,2,2,0]`	Verifies varying segment lengths
`[0,5,5,0]`	Tests a single segment
`[0,1,0,2,0,3,0]`	Tests groups containing one value
`[0,1000,1000,1000,0]`	Confirms large sums are handled correctly
`[0,1,0,1,0,1,0,1,0]`	Stresses repeated segment resets

Edge Cases

One important edge case is a list containing only a single group, such as:

0 -> 5 -> 5 -> 0

A buggy implementation may incorrectly assume there are multiple groups or fail to append the final sum. This implementation correctly processes the final zero and appends the accumulated sum before termination.

Another important edge case is when every group contains exactly one value:

0 -> 1 -> 0 -> 2 -> 0 -> 3 -> 0

This case is useful because it verifies that the algorithm does not accidentally skip segments or merge adjacent groups together. Since the running sum resets after every zero, each value becomes its own node in the result list.

A third important edge case involves many small groups in a very large list. With up to 2 * 10^5 nodes, inefficient algorithms can become problematic. Because this solution processes every node exactly once and uses only constant auxiliary memory, it scales efficiently even for the maximum input size.

Another subtle edge case is ensuring the boundary zeros are never included in the sums. Since the algorithm only adds values when current.val != 0, the zeros act purely as separators and never affect the computed totals.