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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n) due to recursive stack space
| 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) |
Merge Nodes in Between Zeros - Leetcode 2181 - Python • NeetCodeIO • 7,273 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