2181. Merge Nodes in Between Zeros

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.

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

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.