042.md

2181. Merge Nodes in Between Zeros

Difficulty: 🟡 Medium

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:

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^5].
• 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.

Solutions

O(n) solution in Python3

# 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]:
        target = head
        while target and target.next:
            if target.next.val:
                target.val += target.next.val
                target.next = target.next.next
            else:
                if target.next.next is None:
                    target.next = None
                target = target.next
        return head

The given solution iterates through the linked list and merges consecutive nodes with non-zero values. It modifies the list in-place by updating the values and next pointers.

The algorithm works as follows:

1. Initialize a pointer, target, to the head of the linked list.
2. Iterate through the linked list while target and target.next are not None:
   • If target.next.val is non-zero, add its value to the current target node's value, and update the next pointer of target to target.next.next (skipping the next node).
   • If target.next.val is zero, move target to the next node.
3. Return the head of the modified linked list.

The algorithm merges the nodes in-place, eliminating the need for extra space.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. The algorithm iterates through the list once, and each iteration takes constant time.

The space complexity of the algorithm is O(1) since it only uses a constant amount of extra space to store the pointers.

Summary

The given solution modifies the linked list by merging consecutive non-zero nodes and removing the merged nodes. It has a time complexity of O(n) and a space complexity of O(1), making it an efficient solution for the problem at hand.

NB: If you want to get community points please suggest solutions in other languages as merge requests.