2181. Merge Nodes in Between Zeros

Problem

Question

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.

---

Solutions

1. Single Pass with a new LinkedList

Time Complexity: $O(n)$ | Space Complexity: $O(n)$

To solve the problem, we create a new linked list with a dummy head node new_head. We traverse the original linked list in a single pass. For each node in the original list, if its value is not 0, we add its value to temp_sum. When we encounter a node with a value of 0, we create a new node with the value of temp_sum in the output linked list, then reset temp_sum to 0 to start accumulating the sum for the next segment.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val = val
#         self.next = next
 
class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        new_head = ListNode(0)
        new_cur = new_head
        temp_sum = 0
 
        cur = head.next  # Skip the initial 0 node
        while cur:
            if cur.val == 0:
				new_cur.next = ListNode(temp_sum)
				new_cur = new_cur.next
                temp_sum = 0
            else:
                temp_sum += cur.val
            
            cur = cur.next
 
        return new_head.next
 

---

2. 🏆 Single Pass with in-place Modifications

Time Complexity: $O(n)$ | Space Complexity: $O(1)$

We can slightly modify the approach above to achieve O(1)O(1) space complexity. We use a modify pointer to keep track of 0-valued ListNodes, store the sum in their values, and connect them together.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
 
class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
 
        temp_sum = 0
        modify_prev = head
        modify = head
        cur = head.next  # Skip the initial 0 node
        while cur:
            if cur.val == 0:
                modify_prev = modify
                modify.val = temp_sum
                modify.next = cur
                modify = modify.next
                temp_sum = 0
            else:
                temp_sum += cur.val
            
            cur = cur.next
 
        modify_prev.next = None
 
        return head
 

---

3. Recursive

Time Complexity: $O(n)$ | Space Complexity: $O(n)$

We can also approach the problem recursively by breaking it into fragments, where we find the sum of values between 0-valued nodes. In our design, we can guarantee that the head is either 0 or None. We modify the head’s value to store the sum and recursively process the list from the next 0-valued node.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
 
        if not head:
            return None
        
        node = head.next
        node_sum = 0
        while node and node.val != 0:
            node_sum += node.val
            node = node.next
 
        head.val = node_sum
        head.next = self.mergeNodes(node)
 
        return head.next if head.val == 0 else head