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
- Walk the list; whenever a 0 is encountered, start accumulating the following values until the next 0.
- Append a single node with the accumulated sum to the result.
- The list starts and ends with 0, so every accumulated segment is properly delimited.
- 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.