Problem of The Day: Merge Nodes in Between Zeros

Problem Statement

Intuition

We traverse the linked list, accumulating the sum of the node values between two zeroes. Each time we encounter a zero after accumulating a sum, we create a new node with this sum in a new linked list.

Approach

• Initialize a dummy node to start the new linked list.
• Use a pointer to track the current position in the new linked list.
• Traverse the original linked list, maintaining a running sum of the node values.
• Each time a zero is encountered, if the running sum is greater than zero, create a new node with this sum and append it to the new linked list.
• Reset the running sum and continue traversing the original linked list.

Complexity

• Time complexity: O(n)

• Space complexity: O(1)

Code

# 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]:
        dummy = ListNode(-1)
        ret_curr = dummy
        curr = head
        curr_sum = 0
        while curr:
            if curr.val == 0 and curr_sum > 0:
                ret_curr.next = ListNode(curr_sum)
                ret_curr = ret_curr.next
                curr_sum = 0
            else:
                curr_sum += curr.val
            curr = curr.next
        return dummy.next