Scale Engineer

Merge Nodes in Between Zeros

Med
#1986Time: O(N), where N is the number of nodes in the list. We perform a single pass through the list.Space: O(M), where M is the number of segments between zeros. This is because we create a new node for each segment. In the worst case, M can be proportional to N, leading to O(N) space complexity.1 company
Data structures
Linked List
Companies
josh technology

Prompt

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:

  • The number of nodes in the list is in the range [3, 2 * 105].
  • 0 <= Node.val <= 1000
  • There are no two consecutive nodes with Node.val == 0.
  • The beginning and end of the linked list have Node.val == 0.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves iterating through the original linked list and building a new linked list to store the merged nodes. It's straightforward and doesn't alter the input list.

Algorithm

  • Initialize a dummy node and a newTail pointer to build the result list.
  • Initialize currentSum = 0.
  • Iterate through the input list starting from head.next.
  • If the current node's value is not 0, add it to currentSum.
  • If the current node's value is 0, create a new node with currentSum, append it to the result list using newTail, and reset currentSum to 0.
  • After the loop, return dummy.next.

Walkthrough

We'll traverse the original list, keeping track of the sum of values in the current segment (between two zeros). A dummy node is used to simplify the construction of the new list. A tail pointer will track the end of the new list. We start iterating from the node after the initial zero. For each node, if its value is not zero, we add it to a running sum. When we encounter a zero, it signifies the end of a segment. We create a new node with the accumulated sum, append it to our new list, and reset the sum to zero for the next segment. This process continues until we've traversed the entire original list. The final result is the list starting from the dummy node's next pointer.

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode mergeNodes(ListNode head) {        ListNode dummy = new ListNode(0);        ListNode newTail = dummy;        ListNode current = head.next; // Skip the initial 0        int currentSum = 0;         while (current != null) {            if (current.val == 0) {                // End of a segment                if (currentSum > 0) {                    newTail.next = new ListNode(currentSum);                    newTail = newTail.next;                }                currentSum = 0; // Reset for the next segment            } else {                // Accumulate sum                currentSum += current.val;            }            current = current.next;        }        return dummy.next;    }}

Complexity

Time

O(N), where N is the number of nodes in the list. We perform a single pass through the list.

Space

O(M), where M is the number of segments between zeros. This is because we create a new node for each segment. In the worst case, M can be proportional to N, leading to O(N) space complexity.

Trade-offs

Pros

  • Simple to understand and implement.

  • Does not modify the original input list.

Cons

  • Requires extra space to store the new list, which can be significant for large inputs.

Solutions

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeNodes ( ListNode head ) { ListNode dummy = new ListNode (); int s = 0 ; ListNode tail = dummy ; for ( ListNode cur = head . next ; cur != null ; cur = cur . next ) { if ( cur . val != 0 ) { s += cur . val ; } else { tail . next = new ListNode ( s ); tail = tail . next ; s = 0 ; } } return dummy . next ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem