You are given the head of a linked list, which contains a series of integers separated by 0's. The beginning and end of the linked list will have Node.val == 0.
For every two consecutive 0's, merge all the nodes lying in between them into a single node whose value is the sum of all the merged nodes. The modified list should not contain any 0's.
Return the head of the modified linked list.
Example 1:
Input: head = [0,3,1,0,4,5,2,0] Output: [4,11] Explanation: The above figure represents the given linked list. The modified list contains - The sum of the nodes marked in green: 3 + 1 = 4. - The sum of the nodes marked in red: 4 + 5 + 2 = 11.
Example 2:
Input: head = [0,1,0,3,0,2,2,0] Output: [1,3,4] Explanation: The above figure represents the given linked list. The modified list contains - The sum of the nodes marked in green: 1 = 1. - The sum of the nodes marked in red: 3 = 3. - The sum of the nodes marked in yellow: 2 + 2 = 4.
Constraints:
[3, 2 * 105].0 <= Node.val <= 1000Node.val == 0.Node.val == 0.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.
This approach involves traversing the linked list using a single pass while keeping a temporary sum of node values between consecutive zeros. We use a dummy node to help simplify edge cases related to list modifications.
The solution uses a single traversal of the linked list. A dummy node is used to build the new list of merged node values. A temporary variable sum accumulates the values between two zeros. Once a zero is encountered, a new node with sum is appended to the resultant list, and sum is reset.
Time Complexity: O(n), where n is the number of nodes in the linked list as we traverse the list only once.
Space Complexity: O(1), excluding the space needed for the new output list.
Another approach we can take involves recursion to solve each segment between the zeros sequentially. Though iterative is usually preferred for this problem, recursion can offer a more functional programming perspective.
This recursive approach involves a helper function that traverses the linked list, accumulating values between zeros. When a zero is encountered, a node is created with the accumulated sum (if any) and the values reset for subsequent segments.
Time Complexity: O(n)
Space Complexity: O(n) due to recursive stack space
We define a dummy head node dummy, a pointer tail pointing to the current node, and a variable s to record the sum of the values of the current nodes.
Next, we traverse the linked list starting from the second node. If the value of the current node is not 0, we add it to s. Otherwise, we add s to the node after tail, set s to 0, and update tail to the next node.
Finally, we return the node next to dummy.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the linked list.
| Approach | Complexity |
|---|---|
| Single Pass with Dummy Node | Time Complexity: O(n), where n is the number of nodes in the linked list as we traverse the list only once. |
| Recursive Merging and Accumulation | Time Complexity: O(n) |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Single Pass with Dummy Node | O(n) | O(1) | Best general solution. Efficient traversal with constant memory. |
| Recursive Merging and Accumulation | O(n) | O(n) | Useful for practicing recursion or when modeling segments recursively. |
Merge Nodes in Between Zeros - Leetcode 2181 - Python • NeetCodeIO • 8,095 views views
Watch 9 more video solutions →Practice Merge Nodes in Between Zeros with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor