#2181

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Merge Nodes in Between Zeros

This problem requires merging nodes between zeros in a linked list by summing up the values between consecutive zeros.

Problem Statement

You are given the head of a linked list, where the nodes contain integers separated by zeros. The first and last nodes are guaranteed to have a value of zero.

For every pair of consecutive zeros, merge all the nodes between them into a single node where the value is the sum of those nodes. Return the head of the modified list with no zeros remaining.

Examples

Example 1

Input: head = [0,3,1,0,4,5,2,0]

Output: [4,11]

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]

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 * 105].
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.

Solution Approach

Pointer Manipulation

This problem can be efficiently solved using two pointers. One pointer traverses the list, while the other accumulates the sum of values between consecutive zeros. Once a zero is encountered, the accumulated sum is added as a new node, and the process continues.

In-Place Modification

To optimize space, modify the list in-place by updating node values. The merging process involves keeping track of sums and inserting them directly into the original list, thus avoiding the creation of additional data structures.

Single Pass Traversal

The key to solving this problem in linear time is a single pass through the list. By moving a pointer from node to node, summing values between zeros, and inserting the result at the correct position, the list can be modified efficiently.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity of this solution is O(n) where n is the number of nodes in the linked list. This is because we traverse the list once to perform the merging. The space complexity is O(n) due to the space used for storing the modified list and its new nodes.

What Interviewers Usually Probe

Ability to manipulate linked list pointers correctly.
Skill in optimizing space complexity by modifying the list in-place.
Demonstrating an understanding of traversal techniques to achieve linear time complexity.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly update the linked list pointers, leading to incorrect results.
Overcomplicating the problem by creating unnecessary data structures.
Not handling edge cases such as when there are multiple zeros or when the list is very large.

Follow-up variants

Handling lists with multiple consecutive zeros and ensuring correct merging.
Modifying the problem to work with circular linked lists.
Expanding the problem to allow for additional operations, such as multiplying the sums instead of adding them.

FAQ

How do I merge nodes between zeros in a linked list?

You can merge nodes by traversing the list with two pointers, accumulating the sum of values between zeros, and inserting the sum into the modified list.

What is the time complexity of solving the 'Merge Nodes in Between Zeros' problem?

The time complexity is O(n) because the list is traversed only once to merge nodes between zeros.

What is the space complexity for this problem?

The space complexity is O(n), as the modified list is created and new nodes are added.

What is the main pattern used in 'Merge Nodes in Between Zeros'?

The main pattern is linked-list pointer manipulation, where we traverse and modify the list in-place to merge nodes between zeros.

How does GhostInterview help with this problem?

GhostInterview provides guidance on pointer manipulation techniques and efficient space optimization strategies, helping you solve this problem effectively.

terminal

Solution

Solution 1: Simulation

We define a dummy head node $\textit{dummy}$, a pointer $\textit{tail}$ pointing to the current node, and a variable $\textit{s}$ to record the sum of the values of the current nodes.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = tail = ListNode()
        s = 0
        cur = head.next
        while cur:
            if cur.val:
                s += cur.val
            else:
                tail.next = ListNode(s)
                tail = tail.next
                s = 0
            cur = cur.next
        return dummy.next

Continue Practicing

#2296 design a text editor #2326 spiral matrix iv #2180 count integers with even digit sum