LeetCode Solutions Blog

Merge Nodes in Between Zeros

Number: 2299

Difficulty: Medium

Paid? No

Problem Description

Given the head of a linked list where the list starts and ends with a 0 and has values separated by 0's, merge all nodes between two consecutive 0's by summing their values. The final linked list should only consist of the non-zero summed nodes.

Key Insights

The linked list always starts and ends with a 0.
There will be no two consecutive 0's so every group of numbers is clearly delimited.
You need to sum the values between 0's and create a new node for each sum.
A simple linear traversal of the list is sufficient to accumulate sums and build the result.

Space and Time Complexity

Time Complexity: O(n) - We traverse each node of the list exactly once. Space Complexity: O(1) (excluding the space for the output list) - Only a few extra variables are used for computation.

Solution

We traverse the linked list using a pointer and keep an accumulator to sum the values found between zeros. When a 0 is encountered and the sum accumulator is non-zero, we create a new node in the result list with this sum and reset the accumulator. We use a dummy node to easily construct and then return the head of the resulting list. This approach ensures that every group of numbers between zeros is merged appropriately.

Code Solutions

# 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: ListNode) -> ListNode:
        # Create a dummy node to serve as the head of the result list.
        dummy = ListNode(0)
        current_node = dummy  # Pointer used to build the new list
        sum_val = 0  # Accumulator for the sum between zeros

        # Start with the node after the first zero.
        node = head.next
        while node:
            if node.val == 0:
                # When a zero is encountered, create a new node if we have a non-zero sum.
                if sum_val != 0:
                    current_node.next = ListNode(sum_val)
                    current_node = current_node.next
                    sum_val = 0  # Reset for the next segment
            else:
                # Add the value of the current node to the accumulator.
                sum_val += node.val
            node = node.next  # Move to the next node in the list

        # Return the head of the merged linked list.
        return dummy.next