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 0
s, calculate their sum, and then create a new node with that sum. Essentially, you are merging all nodes between two 0
s into a single node with their sum as its value. The requirement is to do this for every sequence of numbers between 0
s within the linked list. In the end, the returned linked list should not contain any 0
s, 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 0
s. 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 0
s 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:
-
Initialize a
dummy
node that will ultimately act as the predecessor of our new list. Initializetail
to also refer to this dummy node. This node is a sentinel to make appending to the list easier. -
Initialize a running sum
s
to0
. This will accumulate the values of the nodes between each pair of0
s in the input list. -
Skip the initial
0
of the input list by settingcur
tohead.next
. We know the list starts with a0
, so there's no need to include it in our sum. -
Begin iterating through the list using a while loop that continues until
cur
isNone
, which will indicate we've reached the end of the list. -
Inside the loop, check if the current node's value is not
0
. If it is not, add the value to the running sums
. If the node's value is0
, 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 to0
in preparation to start summing the next sequence.
- Create a new node with the sum
-
Move
cur
forward in the list to process the next node. -
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. Returndummy.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 EvaluatorExample 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 0
s 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 0
s 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.
Which of the following is a good use case for backtracking?
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first