题目描述
思路解析动画文字版
记住「遇正数累加、遇 0 结算一段」,下面逐帧套它。开头和结尾的 0 只是分隔标志,本身不贡献和。
先看原链表 0→3→1→0→4→5→2→0。注意它首尾都是 0,中间的 0 把正数隔成一段段。我们的任务是把每段求和。
三个 0 分别在 index 0、3、7。它们把中间的正数切成两段:(3, 1) 和 (4, 5, 2)。每段要各自求和,得到两个结果节点。
cur 从 head.next 出发,跳过开头的 0;同时备好累加器 sum = 0、一条空的结果链表。下面 cur 一路往后扫。
cur 走到 index 1,看到正数 3,要把它累进当前段。
sum 加上 3,当前段的和变成 3。继续往后扫,看下一个是数还是 0。
cur 走到 index 2,看到正数 1,要把它累进当前段。
sum 加上 1,当前段的和变成 4。继续往后扫,看下一个是数还是 0。
cur 走到 index 3,看到 0。这是分隔符 0,说明当前这一段结束了。
结算这一段:把段和 4 新建成一个结果节点,接到结果链表的尾巴;然后 sum 归零,准备攒下一段。
cur 走到 index 4,看到正数 4,要把它累进当前段。
sum 加上 4,当前段的和变成 4。继续往后扫,看下一个是数还是 0。
cur 走到 index 5,看到正数 5,要把它累进当前段。
sum 加上 5,当前段的和变成 9。继续往后扫,看下一个是数还是 0。
cur 走到 index 6,看到正数 2,要把它累进当前段。
sum 加上 2,当前段的和变成 11。继续往后扫,看下一个是数还是 0。
cur 走到 index 7,看到 0。这是末尾的 0,最后一段也到此为止。
结算这一段:把段和 11 新建成一个结果节点,接到结果链表的尾巴;然后 sum 归零。这是末尾的 0,所有段都结算完了,答案已经成形。
cur 越过末尾、变成空,遍历结束。原链表从头到尾只扫了这一遍,每个节点都只看了一次。
返回结果链表:4→11。正是两段 (3,1) 和 (4,5,2) 的和 4 与 11,和开头说的一致。
回头看整趟:一个累加器 sum 边扫边攒,遇到 0 就把当前段和产出成一个结果节点、sum 归零。全程一遍扫描、几个变量,时间 O(n)、额外空间 O(1)。
边界:单段、段内多数、每段一个数,都同一套累加加结算覆盖。
两个追问:可复用节点做到严格 O(1);无结尾 0 则末尾补一次结算。
参考代码
from typing import Optional, Listclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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.next复杂度
- 时间：O(n)，从头到尾只扫一遍链表,每个节点访问一次,n 是节点总数
- 空间：O(1)，只用 sum、tail 几个指针;返回的结果链表不计入额外空间
易错点
面试追问把动画讲成自己的话
追问能不能不另建链表、原地做到严格 O(1)?
追问如果不保证以 0 结尾呢?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
从链表中移除节点
LeetCode 2487 · 中等 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题