合并零之间的节点 图解题解
这道题到底在问什么
- 输入
- head=[0,3,1,0,4,5,2,0]
- 输出
- [4,11]
- 输入
- head=[0,1,0,3,0,2,2,0]
- 输出
- [1,3,4]
最优解：一步一步想明白
- 3记住「遇正数累加、遇 0 结算一段」,下面逐帧套它。开头和结尾的 0 只是分隔标志,本身不贡献和。
- 4先看原链表 0→3→1→0→4→5→2→0。注意它首尾都是 0,中间的 0 把正数隔成一段段。我们的任务是把每段求和。
- 5三个 0 分别在 index 0、3、7。它们把中间的正数切成两段:(3, 1) 和 (4, 5, 2)。每段要各自求和,得到两个结果节点。
- 6cur 从 head.next 出发,跳过开头的 0;同时备好累加器 sum = 0、一条空的结果链表。下面 cur 一路往后扫。
- 7cur 走到 index 1,看到正数 3,要把它累进当前段。
- 8sum 加上 3,当前段的和变成 3。继续往后扫,看下一个是数还是 0。
- 9cur 走到 index 2,看到正数 1,要把它累进当前段。
- 10sum 加上 1,当前段的和变成 4。继续往后扫,看下一个是数还是 0。
- 11cur 走到 index 3,看到 0。这是分隔符 0,说明当前这一段结束了。
- 12结算这一段:把段和 4 新建成一个结果节点,接到结果链表的尾巴;然后 sum 归零,准备攒下一段。
- 13cur 走到 index 4,看到正数 4,要把它累进当前段。
- 14sum 加上 4,当前段的和变成 4。继续往后扫,看下一个是数还是 0。
- 15cur 走到 index 5,看到正数 5,要把它累进当前段。
- 16sum 加上 5,当前段的和变成 9。继续往后扫,看下一个是数还是 0。
- 17cur 走到 index 6,看到正数 2,要把它累进当前段。
- 18sum 加上 2,当前段的和变成 11。继续往后扫,看下一个是数还是 0。
- 19cur 走到 index 7,看到 0。这是末尾的 0,最后一段也到此为止。
- 20结算这一段:把段和 11 新建成一个结果节点,接到结果链表的尾巴;然后 sum 归零。这是末尾的 0,所有段都结算完了,答案已经成形。
- 21cur 越过末尾、变成空,遍历结束。原链表从头到尾只扫了这一遍,每个节点都只看了一次。
- 22返回结果链表:4→11。正是两段 (3,1) 和 (4,5,2) 的和 4 与 11,和开头说的一致。
- 23回头看整趟:一个累加器 sum 边扫边攒,遇到 0 就把当前段和产出成一个结果节点、sum 归零。全程一遍扫描、几个变量,时间 O(n)、额外空间 O(1)。
⚠️ 容易写错的地方
✗ 错：cur 从 head 开始
✓ 对：cur 从 head.next 开始
开头就是 0、是分隔符,从它后面第一个数开始累加才干净(从 head 起首次遇 0 会结算出一个 0 段)
✗ 错：结算后忘了把 sum 归零
✓ 对：产出结果节点后立刻 sum = 0
不清零的话下一段会把上一段的和也算进去,结果全错
✗ 错：担心最后一段漏结算
✓ 对：依赖结尾那个 0 触发最后一段的结算
题目保证以 0 结尾,最后一段在遇到末尾 0 时正好被结算,不需额外补
完整代码（Python / C++ / Java）
Python
from typing import Optional, 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
cur = head.next
total = 0
while cur:
if cur.val == 0:
tail.next = ListNode(total)
tail = tail.next
total = 0
else:
total += cur.val
cur = cur.next
return dummy.nextC++
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
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), *tail = &dummy;
int sum = 0;
for (ListNode* cur = head->next; cur; cur = cur->next) {
if (cur->val == 0) { tail->next = new ListNode(sum); tail = tail->next; sum = 0; }
else sum += cur->val;
}
return dummy.next;
}
};Java
import java.util.*;
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), tail = dummy;
int sum = 0;
for (ListNode cur = head.next; cur != null; cur = cur.next) {
if (cur.val == 0) { tail.next = new ListNode(sum); tail = tail.next; sum = 0; }
else sum += cur.val;
}
return dummy.next;
}
}复杂度
时间
O(n)
从头到尾只扫一遍链表,每个节点访问一次,n 是节点总数
空间
O(1)
只用 sum、tail 几个指针;返回的结果链表不计入额外空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 合并零之间的节点 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能不另建链表、原地做到严格 O(1)?+
能。复用每段结尾那个 0 节点(或段首节点)来存这一段的和,用一个写指针 last 把这些复用节点串起来、再把多余节点跳过。本质一样是一遍扫描,只是省掉了新建节点的开销,空间更严格。
如果不保证以 0 结尾呢?+
那就在遍历结束(cur 为空)后判断一下:若当前 sum 还大于 0,说明最后一段没被结尾 0 触发,要再补一次结算把它产出。本题保证以 0 结尾,最后一个 0 已经触发了最后一段,无需额外处理。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 合并零之间的节点 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。