LeetCode 2181: Merge Nodes in Between Zeros (One Pass Segment Sum)
LeetCode 2181Linked ListSimulationToday we solve LeetCode 2181 - Merge Nodes in Between Zeros.
Source: https://leetcode.com/problems/merge-nodes-in-between-zeros/
English
Problem Summary
The linked list starts and ends with 0. Between every two zeros there are positive values. For each segment, compute the sum and output a new list containing these sums.
Key Insight
Each zero is a delimiter. We scan once, accumulate segment sum, and when we hit a zero we append one node with that sum (if sum > 0), then reset.
Algorithm
- Use a dummy head for the answer list.
- Traverse from head.next.
- If node value is non-zero: add to running sum.
- If node value is zero and running sum > 0: append sum node and reset to 0.
Complexity Analysis
Time: O(n).
Space: O(1) extra (ignoring output list nodes).
Common Pitfalls
- Starting traversal from the first zero instead of head.next.
- Forgetting to reset sum after appending.
- Appending an extra zero-sum node at the end.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeNodes(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
int sum = 0;
for (ListNode cur = head.next; cur != null; cur = cur.next) {
if (cur.val == 0) {
if (sum > 0) {
tail.next = new ListNode(sum);
tail = tail.next;
sum = 0;
}
} else {
sum += cur.val;
}
}
return dummy.next;
}
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeNodes(head *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
sum := 0
for cur := head.Next; cur != nil; cur = cur.Next {
if cur.Val == 0 {
if sum > 0 {
tail.Next = &ListNode{Val: sum}
tail = tail.Next
sum = 0
}
} else {
sum += cur.Val
}
}
return dummy.Next
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeNodes(ListNode* head) {
ListNode dummy(0);
ListNode* tail = &dummy;
int sum = 0;
for (ListNode* cur = head->next; cur != nullptr; cur = cur->next) {
if (cur->val == 0) {
if (sum > 0) {
tail->next = new ListNode(sum);
tail = tail->next;
sum = 0;
}
} else {
sum += cur->val;
}
}
return dummy.next;
}
};# 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 = ListNode(0)
tail = dummy
total = 0
cur = head.next
while cur:
if cur.val == 0:
if total > 0:
tail.next = ListNode(total)
tail = tail.next
total = 0
else:
total += cur.val
cur = cur.next
return dummy.next/**
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var mergeNodes = function(head) {
const dummy = new ListNode(0);
let tail = dummy;
let sum = 0;
for (let cur = head.next; cur !== null; cur = cur.next) {
if (cur.val === 0) {
if (sum > 0) {
tail.next = new ListNode(sum);
tail = tail.next;
sum = 0;
}
} else {
sum += cur.val;
}
}
return dummy.next;
};中文
题目概述
链表以 0 开头并以 0 结尾。每两个 0 之间是一段正整数。把每段求和后，按顺序构成新的链表返回。
核心思路
把 0 当作分隔符。一次遍历中累计段和，遇到下一个 0 时就把当前和写入答案链表，并清零继续。
算法步骤
- 用哑节点构建结果链表。
- 从 head.next 开始遍历。
- 遇到非零值，累加到当前段和。
- 遇到零且段和大于 0，就新建一个和节点并重置段和。
复杂度分析
时间复杂度：O(n)。
额外空间复杂度：O(1)（不计输出链表）。
常见陷阱
- 从首个 0 开始处理导致逻辑混乱。
- 写入答案后忘记清零。
- 末尾错误追加一个 0 和节点。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeNodes(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
int sum = 0;
for (ListNode cur = head.next; cur != null; cur = cur.next) {
if (cur.val == 0) {
if (sum > 0) {
tail.next = new ListNode(sum);
tail = tail.next;
sum = 0;
}
} else {
sum += cur.val;
}
}
return dummy.next;
}
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeNodes(head *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
sum := 0
for cur := head.Next; cur != nil; cur = cur.Next {
if cur.Val == 0 {
if sum > 0 {
tail.Next = &ListNode{Val: sum}
tail = tail.Next
sum = 0
}
} else {
sum += cur.Val
}
}
return dummy.Next
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeNodes(ListNode* head) {
ListNode dummy(0);
ListNode* tail = &dummy;
int sum = 0;
for (ListNode* cur = head->next; cur != nullptr; cur = cur->next) {
if (cur->val == 0) {
if (sum > 0) {
tail->next = new ListNode(sum);
tail = tail->next;
sum = 0;
}
} else {
sum += cur->val;
}
}
return dummy.next;
}
};# 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 = ListNode(0)
tail = dummy
total = 0
cur = head.next
while cur:
if cur.val == 0:
if total > 0:
tail.next = ListNode(total)
tail = tail.next
total = 0
else:
total += cur.val
cur = cur.next
return dummy.next/**
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var mergeNodes = function(head) {
const dummy = new ListNode(0);
let tail = dummy;
let sum = 0;
for (let cur = head.next; cur !== null; cur = cur.next) {
if (cur.val === 0) {
if (sum > 0) {
tail.next = new ListNode(sum);
tail = tail.next;
sum = 0;
}
} else {
sum += cur.val;
}
}
return dummy.next;
};
Comments