2181. Merge Nodes in Between Zeros

MediumLinked ListSimulation
Leetcode Link

Problem Description

The task is to transform a given linked list, which has integer values with sequences of non-zero numbers separated by zeros. Important to consider is that the linked list both begins and ends with a 0. The transformation process is to take every sequence of numbers between two 0s, calculate their sum, and then create a new node with that sum. Essentially, you are merging all nodes between two 0s into a single node with their sum as its value. The requirement is to do this for every sequence of numbers between 0s within the linked list. In the end, the returned linked list should not contain any 0s, except those demarcating the start and end of sequences.

Intuition

To solve this problem, we are walking through the linked list node by node while keeping a running sum of the values between 0s. This process begins after skipping the initial 0 node at the head of the list. When we encounter a 0, we know we've reached the end of a sequence, so we create a new node with the running sum and append it to the result list, and reset the sum to 0 to start for the next sequence. We use a dummy node to help us easily return the head of the new transformed list at the end of the process, and a tail node to keep track of the last node in our result list as we are appending new sum nodes.

The dummy and tail nodes initially point to the same dummy node. As we iterate through the original list, whenever we hit a 0, we create a new node (with the current sum), link it to tail.next, and then update tail to point to the new node we just added. This continues until we have gone through the entire input list. In the end, dummy.next points to the head of the new list without the leading 0, having all intermediate 0s removed and replaced by the sum of values between them.

Learn more about Linked List patterns.

Solution Approach

The implementation uses a single pass through the linked list, utilizing a dummy node to simplify the final return and a tail node to keep track of the end of the new linked list being constructed. The algorithm underpinning this solution is a simple traversal of a singly-linked list paired with elementary accumulation of values.

Here's a step-by-step breakdown of the solution implementation:

  1. Initialize a dummy node that will ultimately act as the predecessor of our new list. Initialize tail to also refer to this dummy node. This node is a sentinel to make appending to the list easier.

  2. Initialize a running sum s to 0. This will accumulate the values of the nodes between each pair of 0s in the input list.

  3. Skip the initial 0 of the input list by setting cur to head.next. We know the list starts with a 0, so there's no need to include it in our sum.

  4. Begin iterating through the list using a while loop that continues until cur is None, which will indicate we've reached the end of the list.

  5. Inside the loop, check if the current node's value is not 0. If it is not, add the value to the running sum s. If the node's value is 0, it signifies we've reached the end of a sequence of numbers, and it's time to create a new node with the accumulated sum.

    • Create a new node with the sum s as its value.
    • Append the new node to the list by setting tail.next to this new node.
    • Update tail to refer to the new node, effectively moving our end-of-list marker to the right position.
    • Reset s back to 0 in preparation to start summing the next sequence.
  6. Move cur forward in the list to process the next node.

  7. The loop exits when we've examined every node. At that point, dummy.next will point to the head of our newly constructed list with summed values. Return dummy.next to adhere to the problem's requirement of returning the head of the modified linked list.

The critical data structure used here is the singly-linked list, and the patterns utilized include the runner technique (iterating over the list) and the sentinel node pattern (dummy node for easy return). The solution is efficient, running in O(n) time complexity with O(1) additional space complexity, where n is the number of nodes in the original linked list, as it involves only a single pass through the list and does not allocate any additional data structures that grow with the size of the input.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's assume we have the following linked list:

10 -> 1 -> 2 -> 3 -> 0 -> 4 -> 5 -> 0

We want to transform it to:

10 -> 6 -> 9 -> 0

where each node between two 0s now contains the sum of all original nodes in that range.

We start by creating a dummy node and making both dummy and tail point to it. We'll also initialize our running sum s to 0. Our linked list initially looks like this (with dummy and tail pointing to the first 0):

1dummy -> 0
2  |
3tail

Our running sum s is 0.

Step 1: We initialize our dummy and tail nodes.

1dummy -> 0
2  |
3tail

Step 2: Initialize running sum s to 0.

Step 3: Set cur to head.next to skip the initial 0.

Step 4-6: We iterate through the list, updating the running sum s and creating new nodes as we encounter zeros. The process is as follows:

cur initially points to 1. Since cur.val is not 0, we add it to s.

1s = 1

Move cur to the next node (2). Since cur.val is not 0, we add it to s.

1s = 3

Move cur to the next node (3). Since cur.val is not 0, we add it to s.

1s = 6

cur now points to 0, so we've reached the end of a sequence. We create a new node with value s (which is 6), attach it to tail.next, and update tail to point to the new node.

1dummy -> 0 -> 6
2           |
3         tail

Reset s to 0 since we're starting a new sequence.

Move cur to the next node (4) and repeat the process. Add 4 to s.

1s = 4

Move cur to 5, add to s.

1s = 9

cur points to 0 again, so end of a sequence. Create a new node with value 9, attach it to tail, update tail, and reset s.

1dummy -> 0 -> 6 -> 9
2                 |
3               tail

Since there are no more nodes after this final 0, we've finished iterating through the list.

Step 7: Our new list is ready. Return dummy.next, which is the head of the new transformed list:

10 -> 6 -> 9 -> 0

The resulting list starts and ends with 0, and all nodes in between represent the sum of original sequences, with intermediate 0s removed.

Solution Implementation

1class ListNode:
2    def __init__(self, value=0, next_node=None):
3        self.value = value
4        self.next = next_node
5
6class Solution:
7    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
8        # Create a dummy node which will be the placeholder for the new list's start.
9        dummy_node = tail = ListNode()
10        # Initialize the sum to keep track of the non-zero node values.
11        node_sum = 0
12      
13        # Move the cursor to the next node as we want to skip the initial zero node.
14        current_node = head.next
15      
16        while current_node:
17            # If the current node's value is not zero, add it to the sum.
18            if current_node.value != 0:
19                node_sum += current_node.value
20            else:
21                # If a zero node is encountered, this signals the end
22                # of the segment. We then add a new node with the 
23                # segment's sum to the resultant list.
24                tail.next = ListNode(node_sum)
25                # Move the tail to the new last node.
26                tail = tail.next
27                # Reset the sum for the next segment.
28                node_sum = 0
29            # Move to the next node in the original list.
30            current_node = current_node.next
31      
32        # Return the new list without the initial dummy node.
33        return dummy_node.next
34
1class Solution {
2    public ListNode mergeNodes(ListNode head) {
3        // Create a dummy node to act as the starting point of the new list
4        ListNode dummyNode = new ListNode();
5        // 'sum' will be used to calculate the sum of values between two zeros
6        int sum = 0;
7        // 'currentTail' refers to the current end of the new linked list
8        ListNode currentTail = dummyNode;
9
10        // Start processing nodes after the initial zero node
11        for (ListNode currentNode = head.next; currentNode != null; currentNode = currentNode.next) {
12            if (currentNode.val != 0) {
13                // Add the current node's value to 'sum'
14                sum += currentNode.val;
15            } else {
16                // If a zero node is found, create a new node with the sum and reset 'sum'
17                currentTail.next = new ListNode(sum);
18                // Move 'currentTail' to the new end node
19                currentTail = currentTail.next;
20                sum = 0; // Reset 'sum' as we started a new sum calculation
21            }
22        }
23
24        // Return the next of dummyNode as it the head of the newly formed list
25        return dummyNode.next;
26    }
27}
28
1/**
2 * Definition for singly-linked list.
3 */
4struct ListNode {
5    int val;
6    ListNode *next;
7    ListNode() : val(0), next(nullptr) {}
8    ListNode(int x) : val(x), next(nullptr) {}
9    ListNode(int x, ListNode *next) : val(x), next(next) {}
10};
11
12class Solution {
13public:
14    /**
15     * The function takes the head of a linked list where each node contains an integer. 
16     * It merges consecutive nodes with non-zero values by summing their values, 
17     * and separates sums with zero-valued nodes. It returns the new list without the initial zero node and trailing zeros.
18     *
19     * @param head The head of the provided linked list.
20     * @return The head of the modified linked list.
21     */
22    ListNode* mergeNodes(ListNode* head) {
23        // Dummy node preceding the result linked list
24        ListNode* dummy = new ListNode();
25      
26        // Tail keeps track of the last node of the result list
27        ListNode* tail = dummy;
28      
29        // Variable to accumulate values of nodes until a zero node encountered
30        int sum = 0;
31      
32        // Iterate over nodes starting after the first (dummy) one
33        for (ListNode* current = head->next; current != nullptr; current = current->next) {
34            // If current value is not zero, add to sum
35            if (current->val != 0) {
36                sum += current->val;
37            } else {
38                // If a zero node is reached, add a new node with the accumulated sum to the result list
39                tail->next = new ListNode(sum);
40                tail = tail->next; // Move the tail forward
41                sum = 0; // Reset sum for next segment
42            }
43        }
44        // Return the head of the resulting list
45        return dummy->next;
46    }
47};
48
1// Global function to merge nodes based on the sum between zeros in a linked list
2function mergeNodes(head: ListNode | null): ListNode | null {
3    // Create a dummy node to serve as the start of the new list
4    const dummyNode: ListNode = new ListNode();
5    // This will be the current node we are adding new sums to
6    let currentNode: ListNode = dummyNode;
7    // Initialize the sum
8    let currentNodeSum: number = 0;
9
10    // Iterate through the entire linked list
11    while (head !== null) {
12        // If the current value is zero and we have a non-zero sum 
13        if (head.val === 0 && currentNodeSum !== 0) {
14            // Add new node to our list
15            currentNode.next = new ListNode(currentNodeSum);
16            // Move to the new node
17            currentNode = currentNode.next;
18            // Reset sum for the next set of values
19            currentNodeSum = 0;
20        }
21        // Add the current value to our sum
22        currentNodeSum += head.val;
23        // Move to the next node in the list
24        head = head.next;
25    }
26  
27    // Return the next node as the dummy node is a placeholder
28    return dummyNode.next;
29}
30

Time and Space Complexity

The time complexity of the given code is O(n), where n is the number of nodes in the linked list. This is because the code iterates through each node exactly once. Within each iteration, it performs a constant time operation of adding the node's value to the sum s, or creating a new node when a zero value is encountered. The construction of the new linked list is done in tandem with the traversal of the original list, ensuring that there are no additional passes required.

The space complexity of the code is O(m), where m is the number of non-zero segments separated by zeros in the original linked list. This is due to the fact that a new list is being created where each node represents the sum of a non-zero segment. The space used by the new list is directly proportional to the number of these segments. No additional space is used except for the temporary variables dummy, tail, s, and cur, which do not depend on the size of the input list.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following is a good use case for backtracking?


Recommended Readings