从链表中删去总和值为零的连续节点 图解题解

这道题到底在问什么

输入

head=[1,2,-3,3,1]

输出

[3,1] （前 3 个和为 0，删掉）

最优解：一步一步想明白

1. 3记住「前缀和相等 ⇒ 中间段为 0」。本动画演示的就是代码的两遍法:先建哈希(记最后出现),再跳指针。
2. 4哈希 {0:dummy}在表头前想象一个「虚拟头」,它的前缀和是 0,先记进哈希 {0: dummy}。第一遍:从第 0 个节点开始累加,记每个前缀和「最后出现」的节点。
3. 5哈希 {0:dummy, 1:#0}走到 #0(值 1),前缀和累加到 1。把「1 → #0」记进哈希。
4. 6哈希 {0:dummy, 1:#0, 4:#1}走到 #1(值 3),前缀和累加到 4。把「4 → #1」记进哈希。
5. 7哈希 {0:dummy, 1:#0, 4:#1, 6:#2}走到 #2(值 2),前缀和累加到 6。把「6 → #2」记进哈希。
6. 8哈希 {0:dummy, 1:#0, 3:#3, 4:#1, 6:#2}走到 #3(值 -3),前缀和累加到 3。把「3 → #3」记进哈希。
7. 9哈希 {0:dummy, 1:#4, 3:#3, 4:#1, 6:#2}走到 #4(值 -2),前缀和累加到 1。把「1 → #4」记进哈希(前缀和 1 之前出现过,这里用 #4 覆盖旧的,两遍法只保留每个前缀和「最后出现」的节点)。
8. 10哈希 {0:dummy, 1:#4, 3:#3, 4:#1, 6:#5}走到 #5(值 5),前缀和累加到 6。把「6 → #5」记进哈希(前缀和 6 之前出现过,这里用 #5 覆盖旧的,两遍法只保留每个前缀和「最后出现」的节点)。
9. 11哈希 {0:dummy, 1:#4, 3:#3, 4:#1, 6:#5, 11:#6}走到 #6(值 5),前缀和累加到 11。把「11 → #6」记进哈希。
10. 12哈希 {0:dummy, 1:#4, 3:#3, 4:#1, 6:#7, 11:#6}走到 #7(值 -5),前缀和累加到 6。把「6 → #7」记进哈希(前缀和 6 之前出现过,这里用 #7 覆盖旧的,两遍法只保留每个前缀和「最后出现」的节点)。
11. 13哈希 {0:dummy, 1:#4, 3:#3, 4:#1, 6:#7, 11:#6}第一遍走完,哈希里每个前缀和都指向它「最后一次」出现的节点。注意前缀和 1 → #4、前缀和 6 → #7(都被后面的覆盖成最后位置)。第二遍就靠它一步跳过零和段。
12. 14哈希就绪 {0:dummy, 1:#4, 3:#3, 4:#1, 6:#7, 11:#6}哈希已建好。第二遍再从虚拟头走一遍:在每个节点处,用「当前前缀和最后出现处的下一个」直接接上,一步跳过零和段。
13. 15cur = dummy,前缀和 0cur 从虚拟头出发,前缀和 0。查哈希 {0:dummy},dummy.next 仍是第 0 个,不变。cur 前进到第 0 个节点。
14. 16cur = #0,前缀和 1cur 走到 #0,前缀和累加到 1。接下来查哈希:前缀和 1 最后出现在哪个节点。
15. 171 → #4查哈希:前缀和 1 最后出现在 #4。#0 和 #4 前缀和相同,说明 #0 之后到 #4 这一段(#1、#2、#3、#4)总和为 0,下一步一步跳过。
16. 18删 #1,#2,#3,#4让 #0.next = #4.next = #5,中间 #1、#2、#3、#4 整段被跳过(删除,打删除线)。cur 前进到 #5。
17. 19cur = #5,前缀和 6cur 走到 #5,前缀和累加到 6。接下来查哈希:前缀和 6 最后出现在哪个节点。
18. 206 → #7查哈希:前缀和 6 最后出现在 #7。#5 和 #7 前缀和相同,说明 #5 之后到 #7 这一段(#6、#7)总和为 0,下一步一步跳过。
19. 21删 #6,#7让 #5.next = #7.next = null,中间 #6、#7 整段被跳过(删除,打删除线)。cur 前进到 链表末尾,第二遍结束。
20. 22删除段:#1, #2, #3, #4, #6, #7第二遍走完,所有总和为 0 的段都被指针一步步跳过删掉(打删除线):#1、#2、#3、#4、#6、#7。
21. 23结果链表 = [1, 5]剩下绿色的 [1, 5] 就是答案。整条流程:第一遍建「前缀和→最后节点」哈希,第二遍跳指针一次清掉所有零和段。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prefix = 0
        last = {}
        cur = dummy
        while cur:
            prefix += cur.val
            last[prefix] = cur
            cur = cur.next
        prefix = 0
        cur = dummy
        while cur:
            prefix += cur.val
            cur.next = last[prefix].next
            cur = cur.next
        return dummy.next

#include <unordered_map>
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* removeZeroSumSublists(ListNode* head) {
        ListNode dummy(0, head);
        unordered_map<int, ListNode*> last;
        int prefix = 0;
        for (ListNode* cur = &dummy; cur; cur = cur->next) {
            prefix += cur->val;
            last[prefix] = cur;
        }
        prefix = 0;
        for (ListNode* cur = &dummy; cur; cur = cur->next) {
            prefix += cur->val;
            cur->next = last[prefix]->next;
        }
        return dummy.next;
    }
};

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 removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        Map<Integer, ListNode> last = new HashMap<>();
        int prefix = 0;
        for (ListNode cur = dummy; cur != null; cur = cur.next) {
            prefix += cur.val;
            last.put(prefix, cur);
        }
        prefix = 0;
        for (ListNode cur = dummy; cur != null; cur = cur.next) {
            prefix += cur.val;
            cur.next = last.get(prefix).next;
        }
        return dummy.next;
    }
}

复杂度

面试官可能追问