数组与链表｜LeetCode 第一轮复盘

章节状态：已完成 7/8。目前 LC 206、876、203、83、21、141、160 已完成并复盘；LC 707 暂缓。当前主要训练目标不是记住单题代码，而是稳定理解节点身份、指针职责、None 安全检查、修改 next 前的信息保存，以及如何通过相对速度或路径对齐揭示链表结构。

一、第 2 组题目清单

顺序	LeetCode	难度	题目	核心训练	当前状态
1	206	简单	Reverse Linked List	三指针、原地反转	已复盘
2	876	简单	Middle of the Linked List	快慢指针、None 检查	已复盘
3	203	简单	Remove Linked List Elements	删除节点、虚拟头节点	已复盘
4	83	简单	Remove Duplicates from Sorted List	连续节点、修改 next	已复盘
5	21	简单	Merge Two Sorted Lists	双链表指针、虚拟头节点	已复盘
6	141	简单	Linked List Cycle	快慢指针、环	已复盘
7	160	简单	Intersection of Two Linked Lists	节点身份、路径对齐	已复盘
8	707	中等	Design Linked List	综合实现链表操作	暂缓

二、链表的基础心智模型

1. head 是什么

head 是保存第一个节点引用的变量。它本身只指向一个 ListNode 对象，但通过该节点的 next 可以继续访问后面的整个链条。

head
 ↓
[1 | next] → [2 | next] → [3 | None]

因此：

“head 是第一个节点的引用”最精确；
“从 head 可以访问整个链表”也正确；
“head 本身就是整个链表”不够精确。

参数类型：

head: Optional[ListNode]

表示 head 可能是第一个节点，也可能是 None，后者代表空链表。

2. 变量保存的是节点引用

slow = fast = head

不是复制两个节点，而是创建两个独立变量，让它们暂时指向同一个节点。之后更新 slow 不会自动更新 fast，更新 fast 也不会自动更新 slow。

3. None 本身合法，访问 None 的属性才报错

fast = fast.next.next

如果 fast.next.next 的结果是 None，赋值完全合法；错误发生在之后继续访问：

fast.next  # fast 已经是 None 时，触发 AttributeError

因此要区分：

表达式返回 None       → 合法
继续访问 None.next    → AttributeError

4. 覆盖 next 前必须保存剩余链表

一个节点通常只有 next 这一条通向后续节点的连接。一旦执行：

current.next = prev

原来的后续连接就被覆盖。如果此前没有保存：

next_node = current.next

可能永久失去尚未处理部分的入口。

三、LC 206. Reverse Linked List

我的原始代码

class Solution:
    def reverseList(
        self,
        head: Optional[ListNode],
    ) -> Optional[ListNode]:

        prev = head
        current = head

        while current is not None:
            next_node = prev.next
            current = next_node.next
            next_node.next = prev
            prev.next = None

        return prev

我的思路

为了反转链表，先拿到一个节点及其下一个节点，将下一个节点的 next 指回前一个节点，再断开旧连接；同时需要一个指针不断追踪尚未处理的部分。

这个思路已经意识到“反转一条边”和“保存剩余链表”两个核心动作，但没有给 prev、current、next_node 建立稳定且互不冲突的职责。

问题与遗漏

1. prev 初始化错误。 开始时尚未反转任何节点，因此已反转部分应为空，prev 应为 None，而不是 head。
2. prev 与 current 职责重叠。 两者同时指向 head，无法分别表示“已反转部分”和“尚未处理部分”。
3. 保存了错误的后继。 应保存 current.next，因为 current 是正在处理的节点；不应通过 prev.next 寻找待处理节点。
4. current = next_node.next 会跳过节点。 下一轮应该处理刚保存的 next_node，因此应写 current = next_node。
5. prev 从未前进。 缺少 prev = current，所以它无法逐步成为反转后链表的新头。
6. 可能访问 None.next。 当 next_node 为 None 时，next_node.next 会触发 AttributeError。
7. 不需要每轮额外执行 prev.next = None。 第一轮中的 current.next = prev 且 prev = None 会自然地让原头节点成为新尾节点。

正确的指针职责

prev       已经反转部分的头节点
current    尚未处理部分的第一个节点
next_node  覆盖 current.next 前临时保存的后继节点

循环不变量：每轮开始时，prev 指向完整的已反转前缀，current 指向完整的未处理后缀；所有原节点仍然可以从这两个入口访问。

正确写法

class Solution:
    def reverseList(
        self,
        head: Optional[ListNode],
    ) -> Optional[ListNode]:

        prev = None
        current = head

        while current is not None:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

        return prev

四个动作的顺序不能随意交换：

next_node = current.next  # 保存剩余链表
current.next = prev       # 反转当前连接
prev = current            # 扩大已反转部分
current = next_node       # 移动到下一个待处理节点

用 1 → 2 → 3 推演

初始：prev = None       current = 1 → 2 → 3
一次：prev = 1          current = 2 → 3
二次：prev = 2 → 1      current = 3
三次：prev = 3 → 2 → 1  current = None

循环结束时，current 表明没有未处理节点，prev 指向反转后链表的新头，因此返回 prev。

重做检查点

• 为什么 prev 必须从 None 开始？
• 为什么修改 current.next 前必须保存 current.next？
• 每次循环结束后，prev 和 current 分别指向哪一部分？
• 空链表和单节点链表是否需要额外分支？

四、LC 876. Middle of the Linked List

我的原始代码

class Solution:
    def middleNode(
        self,
        head: Optional[ListNode],
    ) -> Optional[ListNode]:

        slow, fast = head

        while fast.next is not None:
            slow = slow.next
            fast = fast.next.next

        return slow

正确的总体思路

使用快慢指针：slow 每次走一步，fast 每次走两步。当 fast 走完整条链表时，slow 恰好走过约一半距离。

问题与遗漏

1. 初始化使用了解包语法。 slow, fast = head 会尝试从一个 ListNode 对象中取出两个元素，产生 TypeError。让两个变量指向同一节点应写 slow = fast = head。
2. 循环条件没有检查 fast 本身。 偶数长度链表中，fast 最终会变成 None；下一轮访问 fast.next 会触发 AttributeError。
3. 需要依赖 and 的短路检查。 先判断 fast is not None，只有成立时才访问 fast.next。

正确写法

class Solution:
    def middleNode(
        self,
        head: Optional[ListNode],
    ) -> Optional[ListNode]:

        slow = fast = head

        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

        return slow

为什么 fast.next.next 可以是 None

循环条件只需要保证计算过程中必须访问的对象存在：

fast 必须不是 None
fast.next 必须不是 None

不需要保证 fast.next.next 存在，因为它可以合法地返回 None 并赋给 fast。下一轮先检查 fast is not None，条件为假后，由于 and 的短路行为，不会继续访问 fast.next。

奇偶长度的终止状态

奇数长度：fast 停在最后一个节点，fast.next == None
偶数长度：fast 越过尾节点，fast == None

对于偶数长度链表，题目要求返回两个中间节点中的第二个。因为 slow 和 fast 都从 head 出发，在 fast 走出链表时，slow 正好落在第二个中间节点。

重做检查点

• slow = fast = head 是否创建了节点副本？
• 为什么循环条件必须按 fast、fast.next 的顺序检查？
• fast.next.next 为 None 与访问 None.next 有什么区别？
• 偶数长度时为什么返回第二个中间节点？

五、LC 203. Remove Linked List Elements

我的原始代码

class Solution:
    def removeElements(
        self,
        head: Optional[ListNode],
        val: int,
    ) -> Optional[ListNode]:

        current = head

        while current is not None:
            if current.next.val == val:
                next_node = current.next
                current.next = next_node.next
                next_node.next = None

            current = current.next

        return head

失败用例：

head = [7, 7, 7, 7]
val = 7

正确的总体思路

通过前驱节点修改 next 来跳过待删除节点：

previous.next = node_to_delete.next

原思路已经掌握了删除中间节点的基本方式，但没有覆盖“头节点也要被删除”和“连续节点都等于目标值”的情况。

问题与遗漏

1. 从未检查 current 本身。 判断 current.next.val 只能删除当前节点之后的节点，原来的 head 永远没有前驱，因此无法用同一逻辑删除。
2. 删除后仍然移动 current。 如果新的 current.next 也等于 val，立即前进会跳过它，导致连续目标节点未被完整删除。
3. current.next.val 可能访问 None.val。 循环只保证 current 存在，没有保证 current.next 存在；当 current 是尾节点时会触发 AttributeError。
4. 不需要主动执行 next_node.next = None。 从结果链表中跳过目标节点已经足够；除非有额外资源管理要求，否则不需要手动断开被删除节点。

为什么需要虚拟头节点

虚拟头节点为原来的 head 制造了一个统一前驱：

dummy → head → ...

这样无论目标节点位于头部、中间还是尾部，都可以通过检查和修改 current.next 使用同一套逻辑。

正确写法

class Solution:
    def removeElements(
        self,
        head: Optional[ListNode],
        val: int,
    ) -> Optional[ListNode]:

        dummy = ListNode(0, head)
        current = dummy

        while current.next is not None:
            if current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next

        return dummy.next

为什么删除后不能移动 current

对于：

dummy → 7₁ → 7₂ → 7₃ → 7₄

current 保持指向 dummy，每次删除其后面的一个 7：

dummy → 7₂ → 7₃ → 7₄
dummy → 7₃ → 7₄
dummy → 7₄
dummy → None

只有当 current.next 不需要删除时，才能执行：

current = current.next

重做检查点

• 为什么原 head 无法通过“前驱修改后继”的逻辑直接删除？
• dummy 如何统一头部、中间和尾部删除？
• 为什么删除后停留原地，不删除时才前进？
• 空链表、全部删除、连续目标值和尾节点删除是否安全？

六、LC 83. Remove Duplicates from Sorted List

我的疑问

为什么常见解法需要：

while current is not None and current.next is not None:

其中 current is not None 是否重要？为什么 LC 203 使用虚拟头节点时只需要检查 current.next is not None？

根本原因：能否事先证明 current 一定存在

LC 83 通常从真实头节点开始：

current = head

而 head 的类型是 Optional[ListNode]，空链表时 current 一开始就是 None。直接计算 current.next 等价于访问 None.next，所以必须先检查 current。

LC 203 则从一定存在的虚拟头节点开始：

dummy = ListNode(0, head)
current = dummy

算法只在已经确认 current.next 存在时才把 current 移到该节点，因此循环不变量保证 current 始终是实际节点；显式检查 current is not None 便是多余的。

正确写法

class Solution:
    def deleteDuplicates(
        self,
        head: Optional[ListNode],
    ) -> Optional[ListNode]:

        current = head

        while current is not None and current.next is not None:
            if current.val == current.next.val:
                current.next = current.next.next
            else:
                current = current.next

        return head

只有当前节点和下一个节点都存在，才有两个相邻节点可供比较。删除 current.next 后不能前进，因为新的 current.next 可能仍然重复；不删除时才移动 current。

也可以先处理空链表：

if head is None:
    return None

随后只写 while current.next is not None。因此真正规则不是固定记忆条件数量，而是：访问 current.next 前必须能够证明 current 不是 None，该证明可以来自循环条件、提前返回或循环不变量。

重做检查点

• 空链表时 current 的初始值是什么？
• 为什么处理尾节点时必须检查 current.next？
• 删除重复节点后为什么不移动 current？
• LC 83 与 LC 203 的条件差异来自哪里？

七、LC 21. Merge Two Sorted Lists

我的原始代码中的核心结构

dummy = ListNode(0)

while current1 is not None and current2 is not None:
    if current1.val <= current2.val:
        next_node = current1
        dummy.next = next_node
        current1 = current1.next
    else:
        next_node = current2
        dummy.next = next_node
        current2 = current2.next

问题与遗漏

比较逻辑和“一条链表耗尽后接上另一条链表”的方向正确，但 dummy.next 被反复覆盖。第二次执行 dummy.next = ... 并不是把新节点接在结果尾部，而是替换结果链表的入口，导致之前选择的节点从返回路径中丢失。

必须把两个职责分开：

dummy  固定在结果链表之前，永久保存返回入口
tail   指向结果链表最后一个节点，负责追加节点

正确写法

class Solution:
    def mergeTwoLists(
        self,
        list1: Optional[ListNode],
        list2: Optional[ListNode],
    ) -> Optional[ListNode]:

        dummy = ListNode(0)
        tail = dummy
        current1 = list1
        current2 = list2

        while current1 is not None and current2 is not None:
            if current1.val <= current2.val:
                tail.next = current1
                current1 = current1.next
            else:
                tail.next = current2
                current2 = current2.next

            tail = tail.next

        tail.next = current1 if current1 is not None else current2
        return dummy.next

循环不变量

dummy.next  指向合并结果的第一个节点
tail        指向合并结果的最后一个节点
current1    指向 list1 尚未处理部分
current2    指向 list2 尚未处理部分

开头无需单独判断空链表；如果某个输入为 None，主循环自然跳过，并由最后一行接上另一个输入。next_node = current1 也没有保存新信息，因为它只是为同一节点增加一个别名。

重做检查点

• 为什么 dummy 不能承担移动尾指针的职责？
• 为什么追加时修改 tail.next 而不是 dummy.next？
• 什么时候移动输入指针，什么时候移动 tail？
• 为什么剩余链表可以一次性接到结果尾部？

八、LC 141. Linked List Cycle

我的初始设想

沿着 next 不断前进；如果经过的长度超过原链表长度，或者遇到重复值，就判断存在环。

问题与修正

head 只保存第一个节点的引用，并不提供链表长度；如果链表有环，用遍历预先计算长度本身也不会停止。节点值同样不能用于判环，因为无环链表中可以存在值相同但身份不同的节点。

环的准确判定对象是：

是否再次到达以前的同一个节点对象。

集合方法可以保存访问过的节点对象，时间和空间复杂度均为 O(n)；Floyd 快慢指针则把“重复访问历史”转换成“两个不同速度的指针是否相遇”，将额外空间降到 O(1)。

快慢指针写法

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head

        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

            if slow is fast:
                return True

        return False

快慢指针的核心证明

如果无环，fast 最终到达 None 或停在 next == None 的尾节点。如果有环，二者最终都进入有限的环；每轮 slow 走一步、fast 走两步，所以 fast 相对 slow 每轮前进一个节点。相对位置在环长的模意义下最终必然变为零，此时二者指向同一个节点。

比较必须是节点身份：

slow is fast

而不是节点值。fast.next.next 的结果可以合法地为 None；只有在 fast 已经为 None 后继续访问 fast.next 才会报错，循环条件通过短路判断阻止了这种访问。

重做检查点

• 为什么无法通过预先计算链表长度解决环检测？
• 重复值与重复节点对象有什么区别？
• 为什么快指针不会永远错过慢指针？
• 循环条件为什么只需保证 fast 和 fast.next 存在？

九、LC 160. Intersection of Two Linked Lists

我的初始思路与真正难点

最初考虑先比较两个节点的值，再判断是否为同一节点，并疑惑怎样移动指针才能保证交点有机会被同时比较。实际上无需比较值；相交的定义是两个指针指向同一个节点对象。一旦两条单链表到达同一节点，因为每个节点只有一个 next，后面的整个后缀必然共享。

真正难点不是遍历，而是两个头节点到交点的距离不同。算法需要消除这个初始距离差，使两个指针同步到达交点。

方法一：显式计算并对齐长度

先分别计算长度，让较长链表的指针提前走长度差，再同步移动。此时两个指针到交点或 None 的剩余距离相同，因此必然同时到达。

方法二：交换路径，隐式消除长度差

class Solution:
    def getIntersectionNode(
        self,
        headA: ListNode,
        headB: ListNode,
    ) -> Optional[ListNode]:

        pointer_a = headA
        pointer_b = headB

        while pointer_a is not pointer_b:
            pointer_a = headB if pointer_a is None else pointer_a.next
            pointer_b = headA if pointer_b is None else pointer_b.next

        return pointer_a

设 A、B 的独有部分长度分别为 a、b，公共后缀长度为 c。两个指针分别走组合路径：

pointer_a：A + B
pointer_b：B + A

它们第二次到达公共部分入口之前分别走过：

a + c + b
b + c + a

由加法交换律二者相等，所以原来的长度差被抵消。若存在交点，二者在第一个公共节点相遇；若不存在，二者走过相同总距离后在 None 相遇。

算法不是“让链表产生相交”，而是在不修改任何 next 的前提下，使指针在原本已经存在的交点对齐。

相关技巧的边界

路径交换法能成立，是因为两个指针都有唯一下一步，而且相交后共享完整后缀。可迁移的抽象是：

存在初始距离差
→ 设计相同总路程或固定相对距离
→ 让两个指针在目标位置对齐

它与 LC 19 的固定距离、LC 142 的环入口对齐、LC 287 的隐式链表有思想联系，但不能看到“双指针”就机械套用 A + B = B + A。

重做检查点

• 为什么不能比较 val 判断相交？
• 为什么相交以后整个后缀必然共享？
• A + B 与 B + A 如何消除长度差？
• 无交点时为什么两个指针会在 None 同时停止？

十、当前暴露出的共性问题

1. 指针职责尚未稳定

在 206 中，prev 与 current 同时从 head 开始，说明尚未先定义“已处理部分”和“未处理部分”。写循环之前，应先用一句话定义每个变量的职责，并保证这些职责不会在循环中改变。

2. 修改连接后没有重新判断当前位置

203 中删除 current.next 后仍然移动 current，说明没有考虑修改连接后出现的新邻接关系。链表结构发生变化时，应先判断当前位置是否仍有待处理工作，再决定是否前进。

3. 对 None 的检查层级需要更精确

访问：

node.next.val

至少需要确认：

node 不是 None
node.next 也不是 None

而把某个表达式的结果赋为 None 本身并不报错。错误发生在继续访问该 None 的属性时。

4. 需要区分“节点”和“节点引用变量”

head、current、prev、slow、fast 都是保存节点引用的变量。多个变量可以指向同一节点，也可以独立移动；给变量重新赋值只会改变该变量指向哪里，而修改 node.next 才会改变链表结构。

5. 需要区分固定入口与移动尾部

LC 21 中 dummy 必须永久保存结果入口，tail 才负责移动。只要一个算法既需要最终返回链表头，又需要不断向后追加节点，通常就需要两个不同指针承担这两个职责。

6. 需要区分节点值与节点身份

LC 141 和 LC 160 判断的是是否为同一个节点对象，而不是 val 是否相同。不同节点可以保存相同值；同一个节点由不同路径到达时才意味着环或相交。

7. 双指针的本质是维护相对关系

LC 876 使用 2:1 速度获得中点，LC 141 使用速度差揭示环，LC 160 使用相同总路程消除长度差。双指针不是固定模板，而是通过速度、距离或路径安排维护一个有用的相对关系。

十一、链表题统一检查清单

1. 每个指针变量分别代表什么？其职责是否在循环中保持不变？
2. 当前修改的是变量指向，还是节点的 next 结构？
3. 覆盖 next 之前，是否已经保存通向剩余链表的入口？
4. 当前节点或其 next 是否可能为 None？访问属性前是否完成检查？
5. 原 head 是否可能发生变化？如果可能，是否需要 dummy？
6. 删除节点以后应该前进，还是留在原位检查新的邻接关系？
7. 返回的是原 head、dummy.next、prev，还是另一个新头节点？为什么？
8. 空链表、单节点、全部删除、连续目标值、奇数长度和偶数长度是否覆盖？
9. 比较的是节点值还是节点身份？题目真正要求哪一种？
10. 两个指针之间维持的是速度关系、固定距离，还是相同总路程？
11. 如果使用 dummy，它是固定入口还是移动指针？是否还需要单独的 tail？

十二、延迟重做安排

在 3～7 天后从空白重做：

206、876、203、83、21、141、160

完成标准不只是通过测试，还应能够说明：

• 每个指针的准确职责；
• 每轮循环前后的链表结构；
• 为什么不会丢失剩余节点；
• 为什么不会访问 None 的属性；
• 为什么最终返回的变量是新链表的入口。

LC 707 暂时不纳入本轮验收。若能够在不参考答案的情况下实现其余七题，并解释每个指针的职责、终止条件与结构不变量，可以将本组基础链表部分标记为稳定掌握。