Merge Nodes in Between Zeros

Medium

Asked by:

14 views

Topics:

Linked Lists

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 * 10⁵].
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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for the positive integers in the linked list?
Can I modify the existing linked list in-place, or do I need to create a new one?
What should I return if the input linked list is empty (besides just the starting and ending 0s)?
Is the input guaranteed to have at least one sequence of nodes between two 0s?
Can the input list contain values that are non-integer or floating-point numbers?

Brute Force Solution

Approach

The brute force method for merging nodes between zeros means we'll rebuild the list step-by-step. We look for segments defined by zeros and calculate the sum of the values in between. Then, we overwrite the original list with the new merged values.

Here's how the algorithm would work step-by-step:

Start with an empty new list.
Go through the original list from beginning to end.
Whenever you encounter a zero, start a new segment.
Add up all the numbers you see between the zeros to get the sum of that segment.
Once you hit the next zero, add the sum to the new list.
Repeat the process until you reach the end of the original list.
Replace the original list with the new list containing the sums between the zeros.

Code Implementation

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

def mergeNodes(head):
    new_list_head = None
    new_list_tail = None
    current = head.next
    segment_sum = 0

    while current:
        if current.val != 0:
            segment_sum += current.val
        else:
            # We found the end of a segment
            new_node = ListNode(segment_sum)

            if not new_list_head:
                # Initialize the new list with the first segment
                new_list_head = new_node
                new_list_tail = new_node
            else:
                new_list_tail.next = new_node
                new_list_tail = new_node

            segment_sum = 0

        current = current.next

    return new_list_head

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list once to identify segments between zeros and calculate their sums. In the worst case, it visits each node exactly once to compute the sums. The operation of replacing the values in the original list also takes at most n steps, where n is the number of nodes in the linked list. Thus, the time complexity is directly proportional to the number of nodes, resulting in O(n).

Space Complexity

O(N) – The brute force method, as described, creates a new list to store the sums between the zeros. In the worst case, if there are N/2 segments separated by zeros in a list of N nodes (where N is the number of nodes in the linked list), the new list could grow to a size proportional to N. Therefore, the auxiliary space required is linearly dependent on the size of the original linked list, resulting in O(N) space complexity.

Optimal Solution

Approach

The goal is to combine values between zeros in a linked list. The efficient way to do this is to directly modify the original list, avoiding creating a new one. We iterate through the list, accumulating values between zeros and updating the list in place.

Here's how the algorithm would work step-by-step:

Start at the beginning of the list.
Keep a running sum of the values we encounter.
When you reach a zero, replace that zero's value with the running sum.
Reset the running sum to zero to start accumulating for the next section.
Move forward in the list, skipping all the nodes between the replaced zero and the next zero.
Repeat the process of summing, replacing the next zero with the sum, skipping the nodes in between and resetting the sum until we reach the end of the list.
Finally, remove the remaining original nodes (values between zeros) from the linked list, leaving only the sums at the locations of the original zeros.

Code Implementation

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

def mergeNodes(head: ListNode) -> ListNode:
    current_node = head
    running_sum = 0

    while current_node:
        # Accumulate values between zeros
        if current_node.val != 0:
            running_sum += current_node.val
            current_node = current_node.next
        else:
            # Replace zero with running sum
            current_node.val = running_sum
            running_sum = 0

            #Skip nodes in between until next zero
            previous_node = current_node
            current_node = current_node.next
            while current_node and current_node.val != 0:
                next_node = current_node.next
                current_node = next_node
            previous_node.next = current_node

    #Remove the initial dummy node and any trailing nodes
    head = head.next
    current_node = head
    while current_node and current_node.next:
        if current_node.next.val == 0 and current_node.next.next == None:
            current_node.next = None
        else:
            current_node = current_node.next

    return head

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the linked list once. Inside the loop, it accumulates sums and replaces zeros with the sums. It also skips over nodes between the updated zero and the subsequent zero. The number of nodes skipped in total will be less than the number of nodes visited. Because of this the runtime is linearly proportional to the input size, n, which represents the number of nodes in the linked list. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm operates in place, modifying the existing linked list. It uses a constant amount of extra memory for variables like the running sum. No additional data structures that scale with the input size N (where N is the number of nodes in the linked list) are created. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input list	Return null immediately since there's nothing to process.
Linked list with only two zero nodes (0 -> 0)	Modify the list to contain only a single zero node (0), effectively removing the second zero.
Large positive integer sums between zeros that could lead to integer overflow	Use a data type with larger capacity (e.g., long) for the sum to prevent integer overflow.
Input list with a large number of nodes to check for performance.	Iterative solution should provide better performance compared to a recursive solution with large lists.
Linked list contains very large positive integers between zeros.	Ensure chosen data type for storing node values can accommodate these large values.
Consecutive positive integers exist with no leading or trailing zero.	The problem statement specifies it will always start and end with zero so it won't happen.
List contains zeros and only positive integers in between.	The merging logic should correctly sum up all positive integers between the zeros.
All nodes between two zeros are zero	The sum will be zero, and the resulting node will be zero.

Null or empty input list

How to Handle:

Return null immediately since there's nothing to process.

Linked list with only two zero nodes (0 -> 0)

How to Handle:

Modify the list to contain only a single zero node (0), effectively removing the second zero.

Large positive integer sums between zeros that could lead to integer overflow

How to Handle:

Use a data type with larger capacity (e.g., long) for the sum to prevent integer overflow.

Input list with a large number of nodes to check for performance.

How to Handle:

Iterative solution should provide better performance compared to a recursive solution with large lists.

Linked list contains very large positive integers between zeros.

How to Handle:

Ensure chosen data type for storing node values can accommodate these large values.

Consecutive positive integers exist with no leading or trailing zero.

How to Handle:

The problem statement specifies it will always start and end with zero so it won't happen.

List contains zeros and only positive integers in between.

How to Handle:

The merging logic should correctly sum up all positive integers between the zeros.

All nodes between two zeros are zero

How to Handle:

The sum will be zero, and the resulting node will be zero.