Problem

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.

Examples

Example 1:

 graph LR;
	 A(0) --> 3 --> 1 --> B(0) --> 4 --> 5 --> 2 --> C(0)

style 3 fill:#FF9933,stroke:#333,stroke-width:2px;
style 1 fill:#FF9933,stroke:#333,stroke-width:2px;

style 4 fill:#0000FF,stroke:#333,stroke-width:2px;
style 5 fill:#0000FF,stroke:#333,stroke-width:2px;
style 2 fill:#0000FF,stroke:#333,stroke-width:2px;

Outputs:

 graph LR;
	 4 --> 11

style 4 fill:#FF9933,stroke:#333,stroke-width:2px;
style 11 fill:#0000FF,stroke:#333,stroke-width:2px;
  
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 orange: 3 + 1 = 4.
- The sum of the nodes marked in blue: 4 + 5 + 2 = 11.

Example 2:

 graph LR;
	 A(0) --> 1 --> B(0) --> 3 --> C(0) --> T(2) --> U(2) --> D(0)

style 1 fill:#FF9933,stroke:#333,stroke-width:2px;
style 3 fill:#0000FF,stroke:#333,stroke-width:2px;

style T fill:#00FF00,stroke:#333,stroke-width:2px;
style U fill:#00FF00,stroke:#333,stroke-width:2px;

Outputs:

 graph LR;
	 1 --> 3 --> 4

style 1 fill:#FF9933,stroke:#333,stroke-width:2px;
style 3 fill:#0000FF,stroke:#333,stroke-width:2px;
style 4 fill:#00FF00,stroke:#333,stroke-width:2px;
  
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 orange: 1 = 1.
- The sum of the nodes marked in blue: 3 = 3.
- The sum of the nodes marked in green: 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.

Solution

Method 1 - Without creating explicit dummy

Generally, in such problems we use dummy, but in this problem we are already told, that first and last value is 0. So, we have to return the value from 2nd node onwards. So, we can actually use head as dummy. Then, we set start = head.next, and use it to iterate over the list.

Now, we will start traversing from start to the node with value 0 with end pointer, and sum the values.

As, soon as end pointer encounter 0, we will set the value of start with the accumulated sum, and then move start to end.next. We will continue doing it, till we reach the end of list.

Here is the video explanation:

Code

Java
Using dummy
public class Solution {

	public ListNode mergeNodes(ListNode head) {	
		ListNode dummy = head;
		ListNode start = head.next;

		while (start != null) {
			int sum = 0;
			ListNode end = start;
			while (end.val != 0) {
                sum += end.val;
                end = end.next;
            }
            start.val = sum;
            start.next = end.next;
            start = start.next;
		}

		return dummy.next;
	}

}
Getting Rid of dummy completely
public class Solution {

	public ListNode mergeNodes(ListNode head) {	
		head = head.next;
		ListNode start = head;

		while (start != null) {
			int sum = 0;
			ListNode end = start;
			while (end.val != 0) {
                sum += end.val;
                end = end.next;
            }
            start.val = sum;
            start.next = end.next;
            start = start.next;
		}

		return head;
	}

}

Complexity

  • ⏰ Time complexity: O(n) where n is the list size.
  • 🧺 Space complexity: O(1)

Method 2 - Using Recursion

We can also solve this problem recursively, similar to previous method, following these steps:

  • Base Case: If the head.next is null, it returns null.
  • Sum Calculation: The method iterates through the nodes between two 0s to calculate the sum.
  • Assign Sum: The sum is assigned to the node following the first 0.
  • Recursive Call: The function recursively processes the rest of the list and connects the result.
  • Return New Head: The new head of the merged nodes is the node after the first 0.

Code

Java
public class Solution {

	public ListNode mergeNodes(ListNode head) {
		// BASE CASE -> If the list contains only a single zero, return null.
		if (head.next == null) {
			return null;
		}

		// sum the values in the segment
		ListNode curr = head.next;
		int sum = 0;

		while (curr.val != 0) {
			sum += curr.val;
			curr = curr.next;
		}

		// assign sum to the first node between nodes having value 0
		head.next.val = sum;

		// call and get the answer and connect the answer to next of head.next
		head.next.next = mergeNodes(ptr);

		// return head.next => new head
		return head.next;
	}

}

Complexity

  • ⏰ Time complexity: O(n) where n is the list size.
  • 🧺 Space complexity: O(n) assuming stack space