We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Merge Nodes in Between Zeros

Difficulty: Medium

Problem Description

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.

Key Insights

  • The linked list starts and ends with 0's, which act as delimiters for segments to be summed.
  • The nodes between two consecutive 0's need to be summed into a new node.
  • A new linked list will be constructed to hold the sums, avoiding the inclusion of 0's.
  • The problem can be solved using a simple traversal of the linked list while keeping track of the sum of nodes between 0's.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list, as we traverse the list once. Space Complexity: O(1), as we are using a constant amount of space for pointers and sum variables (excluding the space used for the output list).

Solution

To solve the problem, we will use a linked list traversal approach:

  1. Initialize a pointer to iterate through the original list and a variable to keep track of the sum of values between 0's.
  2. When a node with a value of 0 is encountered, we check if we have accumulated a sum. If so, we create a new node with the accumulated sum and add it to a new linked list.
  3. Continue this process until the end of the original list, ensuring we skip over 0's.

The data structure used is a linked list, and the algorithm involves iterating through the list and accumulating sums, followed by creating a new modified linked list.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeNodes(head: ListNode) -> ListNode:
    current = head
    new_head = ListNode(0)  # Dummy head for the new list
    new_current = new_head
    sum_value = 0

    while current:
        if current.val == 0:
            if sum_value > 0:  # Only add if we have a sum to add
                new_current.next = ListNode(sum_value)
                new_current = new_current.next
                sum_value = 0  # Reset sum for the next segment
        else:
            sum_value += current.val  # Accumulate sum
        current = current.next  # Move to the next node

    return new_head.next  # Return the next of dummy head
← Back to All Questions