Merge Nodes in Between Zeros - Video Solutions

Problem Overview: The linked list starts and ends with 0. Between every pair of zeros are positive integers. Your task is to merge each segment by summing the values between the zeros and creating a new node containing that sum.

Approach 1: Single Pass with Dummy Node (O(n) time, O(1) space)

This approach scans the list once while maintaining a running sum of values between zero nodes. When you encounter a 0, the current accumulated sum represents a completed segment. Create a new node with this sum and append it to a result list using a dummy head pointer. Reset the sum and continue traversing until the list ends. The key idea is treating each zero as a boundary marker while iterating through the linked list. Because each node is visited exactly once and no additional data structures are required beyond a few pointers, the algorithm runs in O(n) time with O(1) extra space.

This pattern is common in simulation-style linked list problems. Instead of modifying the original nodes, you construct a clean result list that stores only the computed segment sums. The dummy node simplifies edge cases, especially when inserting the first merged value.

Approach 2: Recursive Merging and Accumulation (O(n) time, O(n) space)

The recursive solution processes segments one at a time using function calls to accumulate values until the next zero appears. Start from the node after the first zero and recursively sum nodes until another zero is reached. When that boundary appears, create a new node containing the accumulated sum and recursively process the rest of the list. Each recursive call handles one segment of numbers between zeros.

This method highlights the natural segmentation of the problem. Each recursive frame represents a segment being merged, which makes the logic easy to reason about. However, recursion adds O(n) stack usage in the worst case. For very long lists, the iterative approach is typically safer and more memory efficient. The recursion pattern is still useful for practicing divide-style traversal on recursive linked list problems.

Recommended for interviews: The single-pass iterative approach with a dummy node is the expected solution. It demonstrates strong pointer manipulation, efficient traversal, and constant extra space usage. Explaining the recursive alternative can show deeper understanding, but interviewers usually prefer the iterative solution because it avoids stack overhead and mirrors real production code patterns.