Merge Nodes in Between Zeros — LeetCode 2181 Python Solution

The problem

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.

Example

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

Python solution

# 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

Complexity

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 2181. Merge Nodes in Between Zeros is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Related problems