⚡Flashcard Drill➔
NeetCode #316LC-2181MediumLinked List
← Back to All Problems

#316 · #2181 · Merge Nodes in Between Zeros(合并零之间的节点)

📌 Problem Statement & Constraints

You are given the head of a linked list where consecutive sequences of nodes are separated by nodes with value 0, and the list begins and ends with 0. Merge each sequence between two zeros into a single node holding the sum, and return the modified list. Constraints: 3 <= number of nodes <= 10^5, 0 <= Node.val <= 1000.

💡 Core Algorithmic Approaches

  1. Walk the list; whenever a 0 is encountered, start accumulating the following values until the next 0.
  2. Append a single node with the accumulated sum to the result.
  3. The list starts and ends with 0, so every accumulated segment is properly delimited.
  4. Build the result with a dummy head to avoid special-casing the first segment.

💻 Benchmark Python3 Implementation

class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = tail = ListNode(0)
        cur = head
        while cur:
            if cur.val == 0:
                total = 0
                cur = cur.next
                while cur and cur.val != 0:
                    total += cur.val
                    cur = cur.next
                if cur:                    # a closing zero exists -> valid segment
                    tail.next = ListNode(total)
                    tail = tail.next
            else:
                cur = cur.next
        return dummy.next

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(1) beyond the output (the new nodes are the result).

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the closing-zero check: the final 0 has no following segment, so an extra zero-sum node would be appended.
  • Summing the zeros themselves: only the values between zeros should be summed.
  • Modifying the input nodes in place: building new nodes is simpler, though in-place modification is also accepted.
  • Assuming the list does not start with 0: the statement guarantees it does, which makes the delimiter logic uniform.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems