INTERVIEW PREPARATION / DATA STRUCTURES

LeetCode 链表专题
15 道题完整学习手册

从保存后继、虚拟头节点到 Floyd 环模型、归并排序与分组翻转。用 Python 3 理解每次指针修改，建立可以反复推演、闭卷复现的面试解题体系。

15 道指定题目6 个学习阶段29 份完整解法单文件 · 完全离线

先定义指针含义，再维护循环不变量；先保存后继，再修改连接；先确认区间边界，再进行局部反转。

使用方式：先读基础与模板，再按阶段练习。每份代码均可单独复制到对应 LeetCode 的 Python 3 编辑器；平台已提供 ListNode 或 Node，无需重复定义。原题链接用于在线练习，离线学习不需要访问网络。学习进度保存在当前浏览器、当前文件环境中，不会自动跨浏览器同步。

学习路线与题目全览

阶段	题目（建议顺序）	阶段目标
第一阶段 · 指针与基础归并	203 移除链表元素 → 206 反转链表 → 21 合并两个有序链表	先建立“节点是对象、next 是引用”的模型，熟练使用虚拟头、前驱和尾指针。验收：能在纸上逐条画出指针修改。
第二阶段 · 局部操作与典型应用	2 两数相加 → 24 两两交换链表中的节点 → 19 删除链表的倒数第 N 个节点	把基础遍历用于进位、相邻交换和倒数定位。验收：能说明每个循环开始时，指针分别指向哪里。
第三阶段 · 快慢指针与环模型	141 环形链表 → 142 环形链表 II → 287 寻找重复数	由判环走向入口证明，再把数组函数跳转映射为链表。验收：能用 a、b、C 证明入口定位。
第四阶段 · 对齐与对称判断	160 相交链表 → 234 回文链表	理解路径对齐和中点分割，区分比较节点身份与比较节点值。验收：判断回文后原链结构恢复。
第五阶段 · 排序与多路归并	148 排序链表 → 23 合并 K 个升序链表	把两链归并扩展为整体排序和 K 路合并，准确核算栈、堆与输入数组空间。验收：写出常量辅助空间的排序版本。
第六阶段 · 复杂指针与分组反转	138 复制带随机指针的链表 → 25 K 个一组翻转链表	管理多种连接关系和局部区间边界。验收：副本完全独立，原链被恢复，短尾不被错误翻转。

先建立链表的对象模型

ListNode 常见构造方式是 ListNode(val=0, next=None)，含 val 与 next 两个属性。head 是指向首节点的引用，空链表用 None 表示；题面 [1,2,3] 是序列化展示，并不是传入函数的 Python 列表。

p = head 只复制引用，不复制节点。p = p.next 移动局部引用；p.next = q 改变节点连接，所有共享该节点的引用都能看到变化。链表随机访问第 i 个节点需要 O(i) 行走，不能套用数组的 O(1) 下标访问直觉。

概念	正确理解	典型使用
值与身份	`a.val == b.val` 比较值；`a is b` 比较同一对象。	回文比较值；相交、判环比较身份。
虚拟头 dummy	只为统一头节点变化而存在，不属于输出。	203、21、24、19、148、23、25。
前驱 prev	修改 prev.next 才能跳过目标或接入新组头。	删除节点、两两交换、分组翻转。
尾指针 tail	输出前缀已完成，tail 指向其最后一个节点。	两链归并、两数相加、多路归并。
快慢指针	步速差或固定间距分别解决不同问题。	中点、Floyd；倒数第 N 个固定差距。
深拷贝	新节点的 next、random 都必须指向新节点或 None。	138 随机链表复制。

统一复杂度口径

通常 n 表示链表节点数，m、n 表示两条链的长度，N 表示 K 条链的总节点数；第 19 题用 L 表示长度，避免与删除位置参数 n 混淆。辅助空间不包含输入与必须返回的结果节点，但包含递归栈、集合、映射和堆。 两数相加与深拷贝即使辅助空间 O(1)，结果仍需要 O(n) 节点。哈希操作的 O(1) 是平均意义，相关时间标为期望时间。

迭代通常更适合长链表。反转链表递归版为题目节点上限调高了 Python 递归上限，但仍需要 O(n) 栈资源；排序的自顶向下版本只有 O(log n) 拆分深度。不要把“复用节点”当作“没有辅助空间”。

空链、单节点、重复值与身份边界

类型	必须检查	预期行为
结构修改	空链、单节点、头部变化、全部删除、连续目标。	返回合法新头，无意外环或丢失后缀。
双指针	偶数 / 奇数长度，n=1、n=L，k=1、k=L、短尾。	指针停止位置与删除 / 比较目标一致。
关系判断	独立同值节点、同一头节点、共享尾部、自环、无环。	用身份判断关系，不修改原结构。
新建结果	最终进位、random=None、自指、跨前后指向、重复值。	新旧节点完全独立，输出编码保持对应关系。

可交互推演：三指针反转

以下把 1 → 2 → 3 逐步反转。每次“下一步”对应完整一轮：保存 nxt、反转 cur.next、更新 prev 和 cur。请先预测下一帧，再点击验证。

第一阶段 · 指针与基础归并

先建立“节点是对象、next 是引用”的模型，熟练使用虚拟头、前驱和尾指针。验收：能在纸上逐条画出指针修改。

01LeetCode 203移除链表元素

前往 LeetCode 原题 ↗

难度：简单｜核心知识点：虚拟头节点 · 前驱指针 · 连续删除

题意与边界

给定单链表 head 和整数 val，删除所有值等于 val 的节点，返回剩余链表的头节点。链表可以为空，也可能所有节点都被删除；节点数最多 10⁴。删除是修改连接关系，不是把节点值设成空。

删除时固定前驱，跳过目标节点。

解法一：虚拟头节点 + 前驱指针（推荐）

解题思路与正确性

在 head 前放一个 dummy，让删除头节点与删除中间节点遵循同一规则。prev 始终指向已处理部分的末尾，待判断节点永远是 prev.next。
若 prev.next.val 等于目标，令 prev.next 跳过它；此时 prev 不动，因为新的 prev.next 还没有检查。否则才把 prev 向后移动。
循环不变量：dummy 到 prev 之间的真实节点均不等于 val；每轮至少移除一个待处理节点或把一个节点纳入已处理部分，因此会终止。

Python 3 · 独立提交

class Solution:
    def removeElements(self, head, val):
        dummy = ListNode(0, head)
        prev = dummy
        while prev.next is not None:
            if prev.next.val == val:
                prev.next = prev.next.next
            else:
                prev = prev.next
        return dummy.next

关键代码解释

关键语句	含义与作用
ListNode(0, head)	哨兵值 0 无业务含义，next 指向原头节点。
prev.next = prev.next.next	绕过目标；prev 仍保留在原位置，以检查连续重复值。
return dummy.next	返回可能发生变化的新头节点。

时间复杂度O(n)，每个原节点至多检查一次。

空间复杂度O(1) 辅助空间，仅一个哨兵和几个引用。

选择建议：边界统一、容易证明，是删除类题目的首选。

解法二：先处理头部，再删除内部节点

解题思路与正确性

先反复移动 head，直到它为空或头节点不再等于 val。这样剩余链表若非空，头节点一定保留。
随后用 cur 检查后继；命中目标时仅跳过后继，未命中时 cur 前进。它与哨兵法保持相同的内部删除逻辑，但需要单独处理头部。

Python 3 · 独立提交

class Solution:
    def removeElements(self, head, val):
        while head is not None and head.val == val:
            head = head.next
        cur = head
        while cur is not None and cur.next is not None:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

关键代码解释

关键语句	含义与作用
while head is not None and head.val == val	不能只写一次 if，否则连续多个目标头节点会残留。
cur is not None and cur.next is not None	兼顾全删后 head 为空的情况。

时间复杂度O(n)，头部与内部合计扫描至多 n 个节点。

空间复杂度O(1) 辅助空间。

选择建议：不创建哨兵，但分支更多；适合对照理解 dummy 消除了什么特殊情况。

示例推演

步骤	操作 / 状态	结果 / 不变量
输入	[1,2,6,6,3]，val = 6	dummy → 1 → 2 → 6 → 6 → 3
保留 1、2	prev 到达节点 2	已处理部分不含 6
第一次删除	2.next 跳到第二个 6	prev 仍在 2
第二次删除	2.next 跳到 3	连续目标没有漏掉
结束	保留 3，后继为空	输出 [1,2,3]

两种解法对照

解法	时间	辅助空间	取舍
虚拟头节点 + 前驱指针（推荐）	O(n)，每个原节点至多检查一次。	O(1) 辅助空间，仅一个哨兵和几个引用。	边界统一、容易证明，是删除类题目的首选。
先处理头部，再删除内部节点	O(n)，头部与内部合计扫描至多 n 个节点。	O(1) 辅助空间。	不创建哨兵，但分支更多；适合对照理解 dummy 消除了什么特殊情况。

易错点与边界检查

删除后无条件移动 prev 会漏掉相邻目标。
不能返回旧 head：输入 [6,1] 时新头节点是 1。
空链表返回 None；[7,7] 删除 7 后也返回 None。

02LeetCode 206反转链表

前往 LeetCode 原题 ↗

难度：简单｜核心知识点：三指针 · 保存后继 · 递归回溯

题意与边界

将单链表所有 next 方向反转，并返回新头节点。节点数范围包含 0，最多 5000；空链表返回 None。要求重连节点，不借助值数组重建。

三指针边界：prev 为反转前缀，cur 为未处理后缀。

解法一：三指针迭代（推荐）

解题思路与正确性

把链表分成已反转部分和未处理部分。prev 是已反转部分的头，cur 是未处理部分的头；初始已反转部分为空。
每轮先用 nxt 保存 cur.next，再把 cur.next 指向 prev，最后更新 prev 与 cur。保存后继发生在改指针之前，是防止丢链的关键。
每轮把一个节点从未处理部分搬到反转部分。cur 为空时，所有节点均已反转，prev 就是新头。

Python 3 · 独立提交

class Solution:
    def reverseList(self, head):
        prev, cur = None, head
        while cur is not None:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        return prev

关键代码解释

关键语句	含义与作用
nxt = cur.next	保存唯一能通向后续链表的引用。
cur.next = prev	只改变当前节点的一条边。
return prev	退出时 cur 是 None，而 prev 指向原尾节点。

时间复杂度O(n)，每个节点处理一次。

空间复杂度O(1) 辅助空间。

选择建议：无递归栈，适合长链表，也是回文和分组翻转的基础。

解法二：递归反转后缀

解题思路与正确性

定义 reverseList(head) 返回整个后缀反转后的头节点。空节点或最后一个节点直接返回。
先反转 head.next 开始的后缀。回溯时原后继已成为后缀尾节点，让它指回 head，再断开 head 原来的 next，防止成环。
新头节点 new_head 从最深层一路原样返回。代码调高递归上限以覆盖本题最多 5000 个节点；实际运行仍依赖 Python 栈资源。

Python 3 · 独立提交

import sys
sys.setrecursionlimit(max(sys.getrecursionlimit(), 20000))

class Solution:
    def reverseList(self, head):
        if head is None or head.next is None:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

关键代码解释

关键语句	含义与作用
new_head = self.reverseList(head.next)	先得到反转后的后缀，例如 3 → 2。
head.next.next = head	head.next 仍指向原后继，通过它把后缀尾接到 head。
head.next = None	切断原正向边，否则局部形成二元环。

时间复杂度O(n)，递归进入和回溯均为线性。

空间复杂度O(n) 递归栈，不能算作 O(1)。

选择建议：递归关系清晰，但空间成本更高；面试要求常量辅助空间时选择迭代。

示例推演

步骤	操作 / 状态	结果 / 不变量
初始	prev = None，cur = 1	未处理 1 → 2 → 3
处理 1	nxt = 2；1.next = None	prev = 1，cur = 2
处理 2	nxt = 3；2.next = 1	prev = 2 → 1，cur = 3
处理 3	nxt = None；3.next = 2	prev = 3 → 2 → 1，cur = None
递归对照	以 3 为新头，回溯接 2，再接 1	两种解法输出均为 [3,2,1]

两种解法对照

解法	时间	辅助空间	取舍
三指针迭代（推荐）	O(n)，每个节点处理一次。	O(1) 辅助空间。	无递归栈，适合长链表，也是回文和分组翻转的基础。
递归反转后缀	O(n)，递归进入和回溯均为线性。	O(n) 递归栈，不能算作 O(1)。	递归关系清晰，但空间成本更高；面试要求常量辅助空间时选择迭代。

易错点与边界检查

先改 cur.next 再读取后继会丢失剩余链表。
最终返回 prev，不是 head 或 cur。
递归版忘记 head.next = None 会产生环；单节点应直接返回自身。

03LeetCode 21合并两个有序链表

前往 LeetCode 原题 ↗

难度：简单｜核心知识点：归并 · 尾指针 · 复用节点

题意与边界

给定两条按非递减顺序排列的链表 list1、list2，把它们的全部节点拼接成一条有序链表并返回头节点。任一链表都可能为空；两个链表各自最多 50 个节点。这里升序允许相同值。

解法一：双指针迭代归并（推荐）

解题思路与正确性

dummy 和 tail 分别固定结果起点、指向结果末尾。只比较两条未处理链的头节点，把较小者接到 tail，再移动对应输入指针。
循环不变量：结果前缀有序，且 tail.val 不大于两个未处理头节点的值。因为输入各自有序，较小头就是所有剩余节点的最小值。
有一条耗尽后，另一条本身仍有序，直接整体挂接。使用 <= 时相等值优先取第一条链，可保留跨链的既定先后次序。

Python 3 · 独立提交

class Solution:
    def mergeTwoLists(self, list1, list2):
        dummy = ListNode(0)
        tail = dummy
        while list1 is not None and list2 is not None:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
        tail.next = list1 if list1 is not None else list2
        return dummy.next

关键代码解释

关键语句	含义与作用
tail = tail.next	每接一个节点，结果尾指针也必须前进。
tail.next = list1 if list1 is not None else list2	剩余链可以直接接上，无需逐个新建节点。

时间复杂度O(m+n) 上界，m、n 是两条输入链的长度。

空间复杂度O(1) 辅助空间；复用原节点，不额外分配结果节点。

选择建议：空间最省，修改输入链的 next；不能承诺输入结构保持不变。

解法二：递归选择较小头节点

解题思路与正确性

若某条链为空，返回另一条。否则选较小的头作为本层结果，把其 next 设置为剩余两条链合并后的头。
每次递归至少消耗一个节点；用相同的 <= 规则保持归并次序。小规模输入下写法简洁，长链表应避免线性深度的递归。

Python 3 · 独立提交

class Solution:
    def mergeTwoLists(self, list1, list2):
        if list1 is None:
            return list2
        if list2 is None:
            return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        list2.next = self.mergeTwoLists(list1, list2.next)
        return list2

关键代码解释

关键语句	含义与作用
if list1 is None	递归终止时整段复用另一条链。
list1.next = self.mergeTwoLists(...)	把子问题的新头接到本层选中的节点后。

时间复杂度O(m+n)。

空间复杂度O(m+n) 最坏递归栈。

选择建议：表达自然，但不能把原地连接误记为常量总辅助空间。

示例推演

步骤	操作 / 状态	结果 / 不变量
输入	A = [1,2,4]；B = [1,3,4]	结果为空
比较 1 与 1	取 A 的 1，再取 B 的 1	[1,1]
比较 2 与 3	取 2，然后取 3	[1,1,2,3]
比较 4 与 4	取 A 的 4；A 耗尽	[1,1,2,3,4]
挂接 B 的剩余段	剩余 [4] 直接接尾	输出 [1,1,2,3,4,4]

两种解法对照

解法	时间	辅助空间	取舍
双指针迭代归并（推荐）	O(m+n) 上界，m、n 是两条输入链的长度。	O(1) 辅助空间；复用原节点，不额外分配结果节点。	空间最省，修改输入链的 next；不能承诺输入结构保持不变。
递归选择较小头节点	O(m+n)。	O(m+n) 最坏递归栈。	表达自然，但不能把原地连接误记为常量总辅助空间。

易错点与边界检查

用 while list1 or list2 却直接访问两者的 val，会在某条为空时出错。
遗漏尾部挂接会丢失较长链的剩余节点。
tail 必须前进；两条都为空时应返回 None。

第二阶段 · 局部操作与典型应用

把基础遍历用于进位、相邻交换和倒数定位。验收：能说明每个循环开始时，指针分别指向哪里。

04LeetCode 2两数相加

前往 LeetCode 原题 ↗

难度：中等｜核心知识点：按位模拟 · 进位 · 新建结果链

题意与边界

两条非空链表表示两个非负整数，每个节点是一位十进制数字，最低位放在链表头。返回和的同样逆序表示。每条链最多 100 个节点；除数字 0 外，原整数没有前导零。这里的“逆序”是位权顺序，无需先反转链表。

解法：逐位相加并传播 carry

解题思路与正确性

两条链从低位同时向高位扫描；缺失的一位按 0 处理。总和 total = x + y + carry，新位为 total % 10，下轮进位为 total // 10。
使用 dummy 与 tail 构建全新结果链。输入指针只前进，不修改输入节点；每轮生成恰好一位。
循环条件必须包含 carry：当两个输入都结束但进位为 1 时，还需要额外创建最高位。由于单次 total 最大 19，carry 始终为 0 或 1。

Python 3 · 独立提交

class Solution:
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode(0)
        tail = dummy
        carry = 0
        while l1 is not None or l2 is not None or carry:
            x = l1.val if l1 is not None else 0
            y = l2.val if l2 is not None else 0
            total = x + y + carry
            carry, digit = divmod(total, 10)
            tail.next = ListNode(digit)
            tail = tail.next
            if l1 is not None:
                l1 = l1.next
            if l2 is not None:
                l2 = l2.next
        return dummy.next

关键代码解释

关键语句	含义与作用
divmod(total, 10)	返回 (商, 余数)，分别是 carry 和当前 digit，顺序不能交换。
or carry	保证 [9] + [1] 的结果是 [0,1]。
ListNode(digit)	创建结果节点，不把输入节点的值或连接改掉。

时间复杂度O(max(m,n))，最多多处理一位最终进位。

空间复杂度O(1) 辅助空间；输出链占 O(max(m,n))，需要单独计入存储总量。

选择建议：直接按位模拟可避免大整数转换，清楚体现链表遍历和进位逻辑。

示例推演

步骤	操作 / 状态	结果 / 不变量
输入	[2,4,3] + [5,6,4]	342 + 465
个位	2 + 5 + 0 = 7	digit = 7，carry = 0
十位	4 + 6 + 0 = 10	digit = 0，carry = 1
百位	3 + 4 + 1 = 8	digit = 8，carry = 0
结果	两个输入与进位均耗尽	[7,0,8]，表示 807
进位边界	[9,9] + [1]	[0,0,1]，表示 100

易错点与边界检查

不要把 [2,4,3] 读成 243，它表示 342。
两条链不等长时，不能无保护地访问空指针。
[0] + [0] 仍应生成一个值为 0 的节点；输出空间不是 O(1)。

05LeetCode 24两两交换链表中的节点

前往 LeetCode 原题 ↗

难度：中等｜核心知识点：局部重连 · 前驱 · 奇数尾部

题意与边界

把相邻节点每两个一组交换，返回新头节点；禁止只交换 val。节点数为 0 到 100；若长度为奇数，最后一个节点保留原位。

prev 接新组头，原 first 成为组尾并接回 rest。

解法一：dummy + 三条边重连（推荐）

解题思路与正确性

prev 指向当前待交换二元组的前驱。把两个节点记为 first、second：原结构 prev → first → second → rest。
先让 first 接上 rest，再让 second 接上 first，最后让 prev 接上 second，得到 prev → second → first → rest。first、second 引用保证修改时节点仍可访问。
交换后 first 成为这组尾节点，它就是下一组的前驱。只有两个节点都存在才交换。

Python 3 · 独立提交

class Solution:
    def swapPairs(self, head):
        dummy = ListNode(0, head)
        prev = dummy
        while prev.next is not None and prev.next.next is not None:
            first = prev.next
            second = first.next
            first.next = second.next
            second.next = first
            prev.next = second
            prev = first
        return dummy.next

关键代码解释

关键语句	含义与作用
first.next = second.next	先接回后缀，避免二元组形成永久环。
prev = first	原第一个节点已变成组尾；跨过整组，而不是只走一步。

时间复杂度O(n)，每组固定次操作。

空间复杂度O(1) 辅助空间。

选择建议：指针含义明确，可自然推广到 K 个一组。

解法二：递归处理后续二元组

解题思路与正确性

空链表或单节点直接返回。先保存第二节点 second，递归交换 second.next 开始的剩余链表。
把原 head 接到递归结果前，再让 second 指回 head，最后返回 second 作为本组新头。递归栈负责保存各组的上下文。

Python 3 · 独立提交

class Solution:
    def swapPairs(self, head):
        if head is None or head.next is None:
            return head
        second = head.next
        head.next = self.swapPairs(second.next)
        second.next = head
        return second

关键代码解释

关键语句	含义与作用
self.swapPairs(second.next)	每次递归跳过两个节点，处理下一整组。
return second	本组原第二节点成为新头。

时间复杂度O(n)。

空间复杂度O(n) 递归栈，层数约 n/2。

选择建议：短而易读，但要求 O(1) 辅助空间时应使用迭代。

示例推演

步骤	操作 / 状态	结果 / 不变量
输入	dummy → 1 → 2 → 3 → 4 → 5	prev = dummy
第一组	first = 1，second = 2	dummy → 2 → 1 → 3 → 4 → 5
移动前驱	prev = 1	下一组为 3、4
第二组	first = 3，second = 4	dummy → 2 → 1 → 4 → 3 → 5
奇数尾部	5 没有配对节点，停止	输出 [2,1,4,3,5]

两种解法对照

解法	时间	辅助空间	取舍
dummy + 三条边重连（推荐）	O(n)，每组固定次操作。	O(1) 辅助空间。	指针含义明确，可自然推广到 K 个一组。
递归处理后续二元组	O(n)。	O(n) 递归栈，层数约 n/2。	短而易读，但要求 O(1) 辅助空间时应使用迭代。

易错点与边界检查

交换 val 违反题目要求，也掩盖了指针训练目标。
prev 需移动到原 first，而不是 second。
检查 prev.next 后，才能读取 prev.next.next；空链和单节点均不交换。

06LeetCode 19删除链表的倒数第 N 个节点

前往 LeetCode 原题 ↗

难度：中等｜核心知识点：固定间距双指针 · dummy · 前驱定位

题意与边界

给定非空链表和 n，删除倒数第 n 个节点，返回新头。题目保证 1 ≤ n ≤ 链表长度，节点最多 30 个。进阶要求一次扫描；删除头节点和尾节点都应正确处理。

解法一：保持 n+1 条边的间距（推荐）

解题思路与正确性

fast、slow 均从 dummy 出发，让 fast 先前进 n+1 步。把 dummy 记为位置 0，真实节点编号为 1…L，None 是位置 L+1。
之后两者同步前进，始终保持位置差 n+1。fast 到达 None 时，slow 位于 L−n，正好是目标节点 L−n+1 的前驱。
执行 slow.next = slow.next.next，再返回 dummy.next。本题 n 合法，因此初始化的 n+1 步不会在 None 上继续取 next。

Python 3 · 独立提交

class Solution:
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0, head)
        fast = slow = dummy
        for _ in range(n + 1):
            fast = fast.next
        while fast is not None:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next

关键代码解释

关键语句	含义与作用
range(n + 1)	本实现让 fast 最终停在 None；与只走 n 步、停在尾节点的写法不能混搭。
slow.next = slow.next.next	slow 指向前驱，才有能力删除目标。

时间复杂度O(L)，fast 单向扫到尾，slow 只扫其中一段，属于一趟双指针扫描。

空间复杂度O(1) 辅助空间。

选择建议：满足一趟扫描要求，关键是固定一套起点、间距、停止位置。

解法二：先统计长度，再定位前驱

解题思路与正确性

第一遍计算 L。目标是正数第 L−n+1 个节点；从 dummy 出发走 L−n 步即可到达它的前驱。
第二遍完成定位和删除。它把倒数位置转换为正数位置，推理直观，但不满足一趟扫描的进阶要求。

Python 3 · 独立提交

class Solution:
    def removeNthFromEnd(self, head, n):
        length = 0
        cur = head
        while cur is not None:
            length += 1
            cur = cur.next
        dummy = ListNode(0, head)
        prev = dummy
        for _ in range(length - n):
            prev = prev.next
        prev.next = prev.next.next
        return dummy.next

关键代码解释

关键语句	含义与作用
range(length - n)	移动到前驱；若 n == length，移动 0 步，prev 保持 dummy。

时间复杂度O(L)，两遍遍历仍是线性。

空间复杂度O(1) 辅助空间。

选择建议：适合先独立写对，再优化成固定间距版本。

示例推演

步骤	操作 / 状态	结果 / 不变量
输入	[1,2,3,4,5]，n = 2	dummy 位置 0
fast 先走 3 步	fast = 节点 3，slow = dummy	间距为 3 条边
同步一步	fast = 4，slow = 1	间距不变
同步两步	fast = 5，slow = 2	间距不变
同步三步	fast = None，slow = 3	跳过 slow.next，即节点 4
结果	3.next 指向 5	输出 [1,2,3,5]

两种解法对照

解法	时间	辅助空间	取舍
保持 n+1 条边的间距（推荐）	O(L)，fast 单向扫到尾，slow 只扫其中一段，属于一趟双指针扫描。	O(1) 辅助空间。	满足一趟扫描要求，关键是固定一套起点、间距、停止位置。
先统计长度，再定位前驱	O(L)，两遍遍历仍是线性。	O(1) 辅助空间。	适合先独立写对，再优化成固定间距版本。

易错点与边界检查

不要把“领先 n 步、fast 停在尾”与本代码“领先 n+1 步、fast 停在 None”混用。
输入 [1]、n=1 时返回 None，必须允许 dummy 成为前驱。
n 是题目参数，和其他题复杂度中的节点数 n 含义不同；本题用 L 表示长度。

第三阶段 · 快慢指针与环模型

由判环走向入口证明，再把数组函数跳转映射为链表。验收：能用 a、b、C 证明入口定位。

07LeetCode 141环形链表

前往 LeetCode 原题 ↗

难度：简单｜核心知识点：Floyd 判环 · 节点身份 · 空指针保护

题意与边界

判断从 head 沿 next 行走是否会再次到达同一节点。若有环返回 True，否则返回 False。pos 只是题面构造尾部连接位置的说明，不传入函数。节点值可以相同，因此值重复不能作为有环依据。

尾节点 −4 指回节点 2，环长为 3；相同值不用于判断环。

解法一：快慢指针 Floyd（推荐）

解题思路与正确性

slow 每轮走一步，fast 每轮走两步；先移动再判断是否是同一个节点，避免把初始同在 head 当作相遇。
若无环，fast 或 fast.next 会先到 None。若有环，两者最终都进入环：每轮 fast 相对 slow 多走一步，在长度为 C 的环上至多 C 轮就会追上。
节点比较用 is 表达身份相同，不比较 val。整个过程只读 next，不修改链表。

Python 3 · 独立提交

class Solution:
    def hasCycle(self, head):
        slow = 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 is not None and fast.next is not None	短路判断让 fast.next.next 的读取安全。
if slow is fast	需要同一节点对象；两个值为 1 的不同节点不算相遇。

时间复杂度O(n)，n 为从头可达的不同节点数；入环前与环内步数均为线性。

空间复杂度O(1) 辅助空间。

选择建议：满足常量空间要求，是检测函数迭代环的通用方法。

解法二：哈希集合记录访问节点

解题思路与正确性

从 head 依次访问，若当前节点已经在 seen 中，说明沿 next 再次到达了同一节点，存在环。
每次先判断再加入，遇到 None 说明没有环。LeetCode 的 ListNode 使用对象身份哈希，可以直接把节点放入 set。

Python 3 · 独立提交

class Solution:
    def hasCycle(self, head):
        seen = set()
        cur = head
        while cur is not None:
            if cur in seen:
                return True
            seen.add(cur)
            cur = cur.next
        return False

关键代码解释

关键语句	含义与作用
seen.add(cur)	存节点引用，不存 cur.val。
if cur in seen	在向后移动之前检查重复访问。

时间复杂度O(n) 期望时间，基于集合平均 O(1) 操作。

空间复杂度O(n) 辅助空间。

选择建议：最直接，也可扩展为返回入口，但不满足常量辅助空间。

示例推演

步骤	操作 / 状态	结果 / 不变量
结构	3 → 2 → 0 → −4 → 回到 2	slow、fast 初始都在 3
第 1 轮	slow = 2，fast = 0	尚未相遇
第 2 轮	slow = 0，fast = 2	尚未相遇
第 3 轮	slow = −4，fast = −4	同一个节点，返回 True
无环对照	[1,1]，尾部指向 None	虽然值重复，仍返回 False

两种解法对照

解法	时间	辅助空间	取舍
快慢指针 Floyd（推荐）	O(n)，n 为从头可达的不同节点数；入环前与环内步数均为线性。	O(1) 辅助空间。	满足常量空间要求，是检测函数迭代环的通用方法。
哈希集合记录访问节点	O(n) 期望时间，基于集合平均 O(1) 操作。	O(n) 辅助空间。	最直接，也可扩展为返回入口，但不满足常量辅助空间。

易错点与边界检查

不能在第一次移动前用 slow is fast 判有环。
pos 不属于提交方法的参数。
空链返回 False；单节点 next 指回自身时返回 True；不能通过改 next 打标记。

08LeetCode 142环形链表 II

前往 LeetCode 原题 ↗

难度：中等｜核心知识点：Floyd 入环点 · 模运算证明 · 双阶段

题意与边界

返回链表入环的第一个节点对象；无环返回 None。禁止修改链表。pos 仅用于描述构造，不传入方法。判环的首次相遇点通常不是入口，还需要第二阶段定位。

s = kC；s = a + b + qC ⇒ a + b ≡ 0 (mod C)

解法一：相遇后重置一个指针（推荐）

解题思路与正确性

第一阶段与 Floyd 判环一致：slow 一步、fast 两步，直到相遇或确认无环。相遇后令 finder 从 head 出发，slow 留在相遇点，两者都一步一步走。
证明：设头到入口距离为 a，环长为 C，入口沿环到相遇点距离为 b，慢指针已走 s 步。因为快指针走 2s、两者相遇，所以 s 是 C 的整数倍；同时 s = a+b+qC，于是 a+b ≡ 0 (mod C)。
因此从相遇点再走 a 步恰好回到入口；从 head 走 a 步也到入口。a>0 时 finder 在前 a 步位于环外，不会提前相遇；a=0 时相遇点就是入口。返回两者再次相遇的节点。

Python 3 · 独立提交

class Solution:
    def detectCycle(self, head):
        slow = fast = head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                finder = head
                while finder is not slow:
                    finder = finder.next
                    slow = slow.next
                return finder
        return None

关键代码解释

关键语句	含义与作用
finder = head	只重置一个指针；另一个留在相遇点。
slow = slow.next	第二阶段两个指针速度都为 1，不再一快一慢。
return finder	返回入口对象，不返回它的值或索引。

时间复杂度O(n)，判环与定位入口的总步数为 O(a+C)。

空间复杂度O(1) 辅助空间。

选择建议：空间最优；证明需要区分路径长度与环上的余数。

解法二：第一次重复访问就是入口

解题思路与正确性

用 seen 记录走过的节点。从 head 沿 next 行走，环外节点只经过一次，进入环后第一轮访问每个环内节点，再次到达入口时出现第一次重复。
因此遇到已在集合中的节点时直接返回它。若走到 None，则无环。此法不需要计算位置或环长。

Python 3 · 独立提交

class Solution:
    def detectCycle(self, head):
        seen = set()
        cur = head
        while cur is not None:
            if cur in seen:
                return cur
            seen.add(cur)
            cur = cur.next
        return None

关键代码解释

关键语句	含义与作用
return cur	第一次重复访问的对象恰好是从 head 进入环的入口。

时间复杂度O(n) 期望时间。

空间复杂度O(n) 辅助空间。

选择建议：直观易验证，适合用作测试参照；常量空间要求下选 Floyd。

示例推演

步骤	操作 / 状态	结果 / 不变量
输入	3 → 2 → 0 → −4 → 2	a = 1，C = 3
第一阶段第 3 轮	slow 与 fast 在 −4 相遇	相遇点不是入口 2
重置	finder = 3，slow = −4	均改成每轮一步
第二阶段第 1 步	finder = 2，slow = 2	返回节点 2
集合对照	依次访问 3、2、0、−4、2	第一次重复为入口节点 2

两种解法对照

解法	时间	辅助空间	取舍
相遇后重置一个指针（推荐）	O(n)，判环与定位入口的总步数为 O(a+C)。	O(1) 辅助空间。	空间最优；证明需要区分路径长度与环上的余数。
第一次重复访问就是入口	O(n) 期望时间。	O(n) 辅助空间。	直观易验证，适合用作测试参照；常量空间要求下选 Floyd。

易错点与边界检查

不能把第一次相遇点直接作为入口。
第二阶段快指针若仍走两步，入口证明不成立。
入口就是 head、自环、无环、空链都要覆盖；节点值相同不代表同一节点。

09LeetCode 287寻找重复数

前往 LeetCode 原题 ↗

难度：中等｜核心知识点：数组建模为函数图 · Floyd · 值域二分

题意与边界

长度为 n+1 的 nums 中，每个值均在 [1,n]，只有一种整数重复，但它可以出现两次以上，其他数至多出现一次。必须不修改数组，只使用 O(1) 额外空间。返回重复的数值。这是一道数组题，通过隐式链表模型纳入本专题。

索引 0 不可能被指回；从 0 出发必有非空环外路径。

解法一：把索引跳转视为链表（推荐）

解题思路与正确性

把索引当节点，定义下一节点 f(i)=nums[i]。从索引 0 出发，由于后续索引始终在 1…n，路径必然进入环，而且 0 不可能在环内。
为什么入口值就是重复数？入口至少有两个不同来源：环外路径进入它的前驱，以及环内指向它的前驱。它们的 nums 值均等于入口索引。题目只有一种重复整数，因此入口索引就是答案。
slow、fast 从 0 起步，先移动后比较；相遇后 finder 从 0 重新走，slow 也改为一步，第二次相遇的索引就是重复值。此模型只有查数组，无需真的构建节点。

Python 3 · 独立提交

class Solution:
    def findDuplicate(self, nums):
        slow = fast = 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        finder = 0
        while finder != slow:
            finder = nums[finder]
            slow = nums[slow]
        return finder

关键代码解释

关键语句	含义与作用
nums[nums[fast]]	两次函数跳转相当于链表 fast.next.next。
finder = 0	与本代码第一阶段的起点一致；不要混用其他初始化版本。
return finder	节点编号本身就是重复数，不必再查一层 nums。

时间复杂度O(n)，可达函数图节点至多 n+1 个。

空间复杂度O(1) 辅助空间，不修改 nums。

选择建议：同时满足不修改、常量空间和线性时间的要求。

解法二：在数值范围上二分计数

解题思路与正确性

在 [1,n] 上二分，不对数组排序。对候选 mid，统计 nums 中 ≤ mid 的元素个数 count。
若重复值 d > mid，1…mid 中没有重复，所以 count ≤ mid。若 d ≤ mid，设 d 出现 r 次，整个值域至多缺失 r−2 个不同值，因此 count 至少为 mid−(r−2)+(r−1)=mid+1。故 count>mid 与 d≤mid 等价，构成单调判定。
count>mid 时把右边界收缩到 mid，否则左边界变为 mid+1。每次只扫描计数，不保存计数数组。

Python 3 · 独立提交

class Solution:
    def findDuplicate(self, nums):
        left, right = 1, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            count = sum(value <= mid for value in nums)
            if count > mid:
                right = mid
            else:
                left = mid + 1
        return left

关键代码解释

关键语句	含义与作用
sum(value <= mid for value in nums)	生成器逐个计数，不创建 O(n) 的布尔列表。
right = mid	mid 本身可能是重复数，不能跳过。

时间复杂度O(n log n)，二分轮数 O(log n)，每轮扫描 O(n)。

空间复杂度O(1) 辅助空间。

选择建议：推理基于抽屉原理，也满足核心限制；速度不及 Floyd。排序或 set 会分别违反不修改或常量空间要求。

示例推演

步骤	操作 / 状态	结果 / 不变量
输入与建模	nums = [1,3,4,2,2]	0 → 1 → 3 → 2 → 4 → 2；入口索引 2
Floyd 第 1、2 轮	(slow,fast) = (1,3)、(3,4)	继续追赶
Floyd 第 3、4 轮	(2,4)、(4,4)	在索引 4 相遇
重置后同步	(finder,slow)：(0,4) → (1,2) → (3,4) → (2,2)	返回 2
二分第 1 轮	[1,4]，mid=2，count=3>2	收缩到 [1,2]
二分第 2 轮	mid=1，count=1≤1	收缩到 [2,2]，输出 2

两种解法对照

解法	时间	辅助空间	取舍
把索引跳转视为链表（推荐）	O(n)，可达函数图节点至多 n+1 个。	O(1) 辅助空间，不修改 nums。	同时满足不修改、常量空间和线性时间的要求。
在数值范围上二分计数	O(n log n)，二分轮数 O(log n)，每轮扫描 O(n)。	O(1) 辅助空间。	推理基于抽屉原理，也满足核心限制；速度不及 Floyd。排序或 set 会分别违反不修改或常量空间要求。

易错点与边界检查

本题值在 [1,n] 是跳转不越界、且 0 不入环的前提，不能套用到任意数组。
重复数可以出现多次，例如 [3,3,3,3,3]；不能只适配恰好重复两次。
不要对 nums 原地排序或原地置负数；Floyd 的比较是整数 ==，链表节点比较才用 is。

第四阶段 · 对齐与对称判断

理解路径对齐和中点分割，区分比较节点身份与比较节点值。验收：判断回文后原链结构恢复。

10LeetCode 160相交链表

前往 LeetCode 原题 ↗

难度：简单｜核心知识点：节点身份 · 路径对齐 · 双指针换头

题意与边界

给定两条无环单链表 headA、headB，返回它们第一个共享的节点对象；不相交返回 None，返回时必须保持原结构。相交指引用到同一个节点；值相同的独立节点不算相交。评测描述中的 intersectVal、skipA、skipB 不是方法参数。

两条路径在 c1 开始共享同一组对象，之后不可能再次分叉。

解法一：走完本链后切换另一条链（推荐）

解题思路与正确性

指针 a、b 分别从 A、B 出发。a 到 None 后改从 B 的头走；b 到 None 后改从 A 的头走。每轮同时走一步。
设独有前缀长度为 x、y，共享后缀长度为 c。发生换头后，到共同入口的步数都是 x+y+c+1（包含从 None 切到另一头的一步），长度差被抵消；如果原长度已相等，会更早在入口相遇。
没有交点时两者最多走过两条完整链和切换步骤，最终同为 None。整个过程只移动局部引用，不连接两条链。

Python 3 · 独立提交

class Solution:
    def getIntersectionNode(self, headA, headB):
        a, b = headA, headB
        while a is not b:
            a = a.next if a is not None else headB
            b = b.next if b is not None else headA
        return a

关键代码解释

关键语句	含义与作用
while a is not b	比较节点身份；两个 None 也视为相遇，统一无交点终止。
else headB	到了 None 后才换头，不是在尾节点直接换头。

时间复杂度O(m+n)，m、n 为两条链长度。

空间复杂度O(1) 辅助空间。

选择建议：无需预先求长度，且不改变任何 next。

解法二：集合记录 A，再扫描 B

解题思路与正确性

先把 A 的所有节点引用放入集合，再从 B 的头开始扫描。B 中首个属于集合的节点就是共同后缀的入口。
因为链表无环，两个输入都能走到 None；集合只需要保存一条链，不需要记录节点值或位置。

Python 3 · 独立提交

class Solution:
    def getIntersectionNode(self, headA, headB):
        seen = set()
        cur = headA
        while cur is not None:
            seen.add(cur)
            cur = cur.next
        cur = headB
        while cur is not None:
            if cur in seen:
                return cur
            cur = cur.next
        return None

关键代码解释

关键语句	含义与作用
if cur in seen	直接询问这个对象是否也出现在 A 中。

时间复杂度O(m+n) 期望时间。

空间复杂度O(m) 辅助空间。

选择建议：易于解释，但比换头法占更多空间；还可先求长度再让长链多走长度差，同样达到常量空间。

示例推演

步骤	操作 / 状态	结果 / 不变量
构造	A: a1 → c1 → c2；B: b1 → b2 → c1 → c2	c1、c2 是共享对象
初始	(a,b) = (a1,b1)	独有前缀不同长
第 1、2 步	(c1,b2) → (c2,c1)	尚未对齐
第 3、4 步	(None,c2) → (b1,None)	开始切换链头
第 5、6 步	(b2,a1) → (c1,c1)	返回共享对象 c1
值相等对照	A=[1]、B=[1]，节点独立	返回 None

两种解法对照

解法	时间	辅助空间	取舍
走完本链后切换另一条链（推荐）	O(m+n)，m、n 为两条链长度。	O(1) 辅助空间。	无需预先求长度，且不改变任何 next。
集合记录 A，再扫描 B	O(m+n) 期望时间。	O(m) 辅助空间。	易于解释，但比换头法占更多空间；还可先求长度再让长链多走长度差，同样达到常量空间。

易错点与边界检查

a.val == b.val 不代表相交。
不能把尾节点临时连起来再忘记恢复；本题的纯读取算法更稳妥。
若没有交点必须能在 None 终止；两条链头相同则直接返回该头。

11LeetCode 234回文链表

前往 LeetCode 原题 ↗

难度：简单｜核心知识点：快慢找中点 · 后半段反转 · 恢复结构

题意与边界

判断单链表从前向后与从后向前的值序列是否相同，返回布尔值。原题链表长度为 1 到 10⁵；这里的代码也兼容空链，按回文处理。进阶要求 O(n) 时间、O(1) 辅助空间。

后半段反转后与前半段比较，最后再反转恢复。

解法一：找中点 + 反转后半段 + 比较并恢复（推荐）

解题思路与正确性

slow、fast 从 head 出发，用 fast.next 和 fast.next.next 判断能否继续。循环结束后，偶数长度时 slow 是前半段最后一个节点，奇数长度时 slow 是中心节点。
反转 slow.next 开始的后半段，随后从 head 与反转后的头同步比较。后半段长度是 floor(n/2)，它耗尽就说明必要的对称位置已全部比较；奇数中心不参与。
发现不等时记录 False 并退出比较，但不立即返回。最后再次反转后半段并接回 slow.next，无论结果真假都恢复原结构。反转辅助函数不递归。

Python 3 · 独立提交

class Solution:
    def isPalindrome(self, head):
        if head is None or head.next is None:
            return True

        def reverse(node):
            prev = None
            while node is not None:
                nxt = node.next
                node.next = prev
                prev, node = node, nxt
            return prev

        slow = fast = head
        while fast.next is not None and fast.next.next is not None:
            slow = slow.next
            fast = fast.next.next
        second = reverse(slow.next)
        left, right = head, second
        result = True
        while right is not None:
            if left.val != right.val:
                result = False
                break
            left, right = left.next, right.next
        slow.next = reverse(second)
        return result

关键代码解释

关键语句	含义与作用
while fast.next is not None and fast.next.next is not None	此版本固定让 slow 停在前半段末尾或中心。
while right is not None	只比较后半段的节点数，不把奇数中心错位比较。
slow.next = reverse(second)	保存后半段头 second，保证比较提前中止后也能完整恢复。

时间复杂度O(n)，找中点、两次反转、比较的总工作仍为线性。

空间复杂度O(1) 辅助空间，无值数组和递归栈。

选择建议：满足进阶要求，结束后保留输入结构；实现细节比数组法多。

解法二：转成值数组比较

解题思路与正确性

顺序收集每个节点的 val，使用左右下标向中间比较。任何一对不等立即返回 False，否则返回 True。
这避免修改 next，不需要恢复输入；代价是 O(n) 值数组。不采用切片反转，以明确展示双指针比较与它的额外开销。

Python 3 · 独立提交

class Solution:
    def isPalindrome(self, head):
        values = []
        cur = head
        while cur is not None:
            values.append(cur.val)
            cur = cur.next
        left, right = 0, len(values) - 1
        while left < right:
            if values[left] != values[right]:
                return False
            left += 1
            right -= 1
        return True

关键代码解释

关键语句	含义与作用
values.append(cur.val)	回文只关心值的对称性，此处存值是正确的。
left < right	中心元素不必和自身重复比较。

时间复杂度O(n)。

空间复杂度O(n) 辅助空间。

选择建议：思路简单且保持输入不变，但不满足常量空间进阶。

示例推演

步骤	操作 / 状态	结果 / 不变量
输入	[1,2,3,2,1]	奇数长度，中心为 3
找中点	slow 从第 1 个走到第 3 个节点	slow.next 指向后半段 [2,1]
反转后半段	[2,1] → [1,2]	second 指向原尾节点
比较	1 对 1，2 对 2	后半段耗尽，中心 3 不比较
恢复	再次反转 [1,2] 并接回	返回 True，原链仍为 [1,2,3,2,1]
非回文	[1,2,3,4] 比较 1 与 4 即失败	仍先恢复后半段，再返回 False

两种解法对照

解法	时间	辅助空间	取舍
找中点 + 反转后半段 + 比较并恢复（推荐）	O(n)，找中点、两次反转、比较的总工作仍为线性。	O(1) 辅助空间，无值数组和递归栈。	满足进阶要求，结束后保留输入结构；实现细节比数组法多。
转成值数组比较	O(n)。	O(n) 辅助空间。	思路简单且保持输入不变，但不满足常量空间进阶。

易错点与边界检查

中点模板和后半段起点必须配套，奇偶边界要分别验证。
若在比较失败时直接 return，会跳过结构恢复。
原题可能有 10⁵ 节点，不适合用线性深度递归反转或递归回文判断。

第五阶段 · 排序与多路归并

把两链归并扩展为整体排序和 K 路合并，准确核算栈、堆与输入数组空间。验收：写出常量辅助空间的排序版本。

12LeetCode 148排序链表

前往 LeetCode 原题 ↗

难度：中等｜核心知识点：归并排序 · 断链 · 自底向上 · 稳定性

题意与边界

把单链表按非递减顺序排序并返回头节点；节点数为 0 到 5×10⁴，包含负数和重复值。进阶要求 O(n log n) 时间与 O(1) 辅助空间。链表不能像数组那样常量时间随机访问，归并排序可直接利用 next 连接。

每轮有序段的长度翻倍，尾部不足整段也正常归并。

解法一：自顶向下归并，先理解分治

解题思路与正确性

少于两个节点时直接返回。slow 从 head、fast 从 head.next 出发找到左半段末尾，保存 right = slow.next 后断开 slow.next，把链表分成两条独立链。
分别递归排序两半，再用迭代归并连接。每层参与归并的总节点数为 n，拆分深度 O(log n)，故时间 O(n log n)。
归并时相等优先取左边，使排序稳定。递归只用于拆分，归并函数迭代，避免归并额外产生 O(n) 深度的递归。

Python 3 · 独立提交

class Solution:
    def sortList(self, head):
        if head is None or head.next is None:
            return head
        slow, fast = head, head.next
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
        right = slow.next
        slow.next = None
        left = self.sortList(head)
        right = self.sortList(right)
        dummy = ListNode(0)
        tail = dummy
        while left is not None and right is not None:
            if left.val <= right.val:
                tail.next, left = left, left.next
            else:
                tail.next, right = right, right.next
            tail = tail.next
        tail.next = left if left is not None else right
        return dummy.next

关键代码解释

关键语句	含义与作用
slow, fast = head, head.next	长度为 2 时 slow 停在第一个节点，保证递归规模缩小。
slow.next = None	物理断开左右两半，不然左递归可能再次看到整条原链。
tail.next, left = left, left.next	Python 先计算右侧引用，再执行赋值，不会因重连丢失旧后继。

时间复杂度O(n log n)，每层拆分与归并总计 O(n)。

空间复杂度O(log n) 辅助空间，来自拆分递归栈；哨兵在回溯归并时使用。

选择建议：较好理解，但递归栈不满足 O(1) 辅助空间进阶。

解法二：自底向上归并（满足进阶）

解题思路与正确性

先统计长度。初始把每个节点看成长度 1 的有序段；每轮按 step 长度切出左右两段，合并后接到结果尾，再把 step 翻倍。
split(node, size) 保留最多 size 个节点，断开其尾部并返回后续起点。先保存 cur = split(right, step)，让未处理后缀在合并前已安全保存。
归并后将较长一侧剩余部分挂上，并沿这段走到真实尾部。每轮这些尾部扫描总共仍是 O(n)，不是嵌套平方；经过 ceil(log₂ n) 轮得到整体有序链。

Python 3 · 独立提交

class Solution:
    def sortList(self, head):
        length, cur = 0, head
        while cur is not None:
            length += 1
            cur = cur.next

        def split(node, size):
            if node is None:
                return None
            for _ in range(size - 1):
                if node.next is None:
                    break
                node = node.next
            rest = node.next
            node.next = None
            return rest

        dummy = ListNode(0, head)
        step = 1
        while step < length:
            prev, cur = dummy, dummy.next
            while cur is not None:
                left = cur
                right = split(left, step)
                cur = split(right, step)
                while left is not None and right is not None:
                    if left.val <= right.val:
                        prev.next, left = left, left.next
                    else:
                        prev.next, right = right, right.next
                    prev = prev.next
                prev.next = left if left is not None else right
                while prev.next is not None:
                    prev = prev.next
            step *= 2
        return dummy.next

关键代码解释

关键语句	含义与作用
cur = split(right, step)	合并前保存下一对待处理段；right 为空时也安全返回 None。
prev.next = left if left is not None else right	挂接本对剩余部分，随后更新真实尾节点。
step *= 2	有序段长度按 1、2、4、8 增长。

时间复杂度O(n log n)，统计 O(n)，每轮切段、归并和尾部扫描合计 O(n)。

空间复杂度O(1) 辅助空间，无递归栈、数组或堆；复用全部真实节点。

选择建议：满足进阶，边界较多；必须检查最后一段不足 step、右段为空等情况。

示例推演

步骤	操作 / 状态	结果 / 不变量
输入	[4,2,1,3]	自底向上版本
step = 1	分组 [4]\|[2] 与 [1]\|[3]	归并后 [2,4,1,3]，每段长度 2 有序
step = 2	分组 [2,4]\|[1,3]	依次取 1、2、3、4
step = 4	step 不小于长度，结束	输出 [1,2,3,4]
自顶向下对照	[4,2]\|[1,3] → 单节点 → [2,4]\|[1,3]	相同归并结果，栈空间不同
不足整段	[3,1,2] 的最后一段可能只有 1 个节点	split 返回 None 时仍能归并，输出 [1,2,3]

两种解法对照

解法	时间	辅助空间	取舍
自顶向下归并，先理解分治	O(n log n)，每层拆分与归并总计 O(n)。	O(log n) 辅助空间，来自拆分递归栈；哨兵在回溯归并时使用。	较好理解，但递归栈不满足 O(1) 辅助空间进阶。
自底向上归并（满足进阶）	O(n log n)，统计 O(n)，每轮切段、归并和尾部扫描合计 O(n)。	O(1) 辅助空间，无递归栈、数组或堆；复用全部真实节点。	满足进阶，边界较多；必须检查最后一段不足 step、右段为空等情况。

易错点与边界检查

自顶向下忘记断链会导致递归不收敛。
递归拆分即使复用节点，也有 O(log n) 栈空间。
自底向上必须在重连前保存下一段；重复值使用 <= 保持稳定；空链返回 None。

13LeetCode 23合并 K 个升序链表

前往 LeetCode 原题 ↗

难度：困难｜核心知识点：最小堆 · 多路归并 · 分治归并 · 同值比较

题意与边界

给定 lists 数组，其中每条链都按非递减顺序排列，合并为一条有序链并返回。K 可以为 0，数组也可包含空链；本题 K 最多 10⁴，总节点数最多 10⁴。以下以 N 表示总节点数、K 表示链表数量。

解法一：最小堆维护每条链的当前头（推荐）

解题思路与正确性

堆中只放每条非空链最前面的未处理节点。因为每条链内部有序，全局最小节点必在这些候选头中。
弹出最小节点并接到输出尾部，再把该节点的后继放回堆。每条链在堆中最多保留一个节点，因此堆大小至多 K。
Python 堆元素用 (node.val, i, node)，i 是输入链编号。同值时先比较不同的整数编号，不会继续比较不可排序的 ListNode；同一链的旧头已弹出再放后继，编号不会同时重复。

Python 3 · 独立提交

from heapq import heapify, heappop, heappush

class Solution:
    def mergeKLists(self, lists):
        heap = [(node.val, i, node)
                for i, node in enumerate(lists) if node is not None]
        heapify(heap)
        dummy = ListNode(0)
        tail = dummy
        while heap:
            _, i, node = heappop(heap)
            nxt = node.next
            tail.next = node
            tail = node
            if nxt is not None:
                heappush(heap, (nxt.val, i, nxt))
        tail.next = None
        return dummy.next

关键代码解释

关键语句	含义与作用
(node.val, i, node)	i 负责打破相同 val 的平局，避免 TypeError。
nxt = node.next	保留该输入链的下一候选，再连接当前节点。
tail.next = None	显式终结输出尾部；空输入时 dummy.next 也为 None。

时间复杂度O(K + N log(K+1))；建堆前需扫描 K 项。常写 O(N log K)，这里用 log(K+1) 覆盖 K≤1，且保留空链扫描成本。

空间复杂度O(K) 辅助空间上界，更精确为 O(H+1)，H 是非空链条数。

选择建议：多路选择清楚，依赖 heapq 标准库，无外部依赖；会复用并修改输入连接。

解法二：原列表中分轮两两归并

解题思路与正确性

第一轮把编号 0 与 1、2 与 3 等合并；第二轮合并长度为 2 的链组；步长 interval 每轮翻倍。
把每次结果直接写回 lists[i]，不用创建一份新的链头数组。每轮每个节点至多参与一次归并，总计 O(log K) 轮。
merge 用迭代实现，不引入递归栈。该版本会改变调用者传入的 lists 数组中的头引用；如果需要保留数组，复制 lists 会额外花 O(K) 空间。

Python 3 · 独立提交

class Solution:
    def mergeKLists(self, lists):
        if not lists:
            return None

        def merge(a, b):
            dummy = ListNode(0)
            tail = dummy
            while a is not None and b is not None:
                if a.val <= b.val:
                    tail.next, a = a, a.next
                else:
                    tail.next, b = b, b.next
                tail = tail.next
            tail.next = a if a is not None else b
            return dummy.next

        interval = 1
        while interval < len(lists):
            for i in range(0, len(lists) - interval, interval * 2):
                lists[i] = merge(lists[i], lists[i + interval])
            interval *= 2
        return lists[0]

关键代码解释

关键语句	含义与作用
len(lists) - interval	只枚举存在配对右组的起点，兼容 K 为奇数。
lists[i] = merge(...)	复用输入头数组存放每轮结果，不分配新数组。

时间复杂度O(K + N log(K+1)) 上界；各轮调度次数总计 O(K)，每轮节点归并 O(N)。

空间复杂度O(1) 辅助空间，不计输入 lists；无递归，但修改头数组。

选择建议：无需堆，辅助空间低。逐条把新链合入增长结果可能达到 O(NK)，分轮平衡归并可避免。

示例推演

步骤	操作 / 状态	结果 / 不变量
输入	[[1,4,5],[1,3,4],[2,6]]	初始候选头为 (1,0)、(1,1)、(2,2)
堆第 1、2 次弹出	取链 0 的 1，补入 4；取链 1 的 1，补入 3	输出前缀 [1,1]
继续取最小	2、3、4、4、5、6	输出 [1,1,2,3,4,4,5,6]
分治第 1 轮	合并前两条 → [1,1,3,4,4,5]	第三条 [2,6] 留待下一轮
分治第 2 轮	合并组 0 与组 2	得到同样的完整输出
边界	lists=[] 或 lists=[[],[]]	返回 None

两种解法对照

解法	时间	辅助空间	取舍
最小堆维护每条链的当前头（推荐）	O(K + N log(K+1))；建堆前需扫描 K 项。常写 O(N log K)，这里用 log(K+1) 覆盖 K≤1，且保留空链扫描成本。	O(K) 辅助空间上界，更精确为 O(H+1)，H 是非空链条数。	多路选择清楚，依赖 heapq 标准库，无外部依赖；会复用并修改输入连接。
原列表中分轮两两归并	O(K + N log(K+1)) 上界；各轮调度次数总计 O(K)，每轮节点归并 O(N)。	O(1) 辅助空间，不计输入 lists；无递归，但修改头数组。	无需堆，辅助空间低。逐条把新链合入增长结果可能达到 O(NK)，分轮平衡归并可避免。

易错点与边界检查

堆元组只写 (val,node) 时，相等值会触发节点比较错误。
N 是总节点数，K 是链数，不能把复杂度误写成只有 O(K log K)。
题目输入是独立无环链；若自行构造测试，应避免两条输入共享尾部导致同一节点被重复接入。

第六阶段 · 复杂指针与分组反转

管理多种连接关系和局部区间边界。验收：副本完全独立，原链被恢复，短尾不被错误翻转。

14LeetCode 138复制带随机指针的链表

前往 LeetCode 原题 ↗

难度：中等｜核心知识点：深拷贝 · 身份映射 · 交织拆分 · 恢复原链

题意与边界

原题现名“随机链表的复制”。节点类 Node 含 val、next、random；random 可指向链上任意节点或 None。创建全新节点，保持 next 与 random 的对应关系，且任何复制指针都不能指回原节点。next 链长度为 0 到 1000，random 可以自指、回指或构成环。

交织结构把“旧节点 → 新节点”的映射藏在 next 中。

解法一：两遍哈希映射（优先掌握）

解题思路与正确性

第一遍只沿 next 走，为每个旧节点创建对应新节点，存入 copies[旧节点]。把 None 也映射到 None，可统一空指针处理。
第二遍仍只沿 next 走，根据已有映射设置新节点的 next 与 random。必须先创建完所有节点，再连接任意指向，才能支持 random 指向尚未遍历到的后方节点。
映射的键必须是旧节点对象而不是值：两个相同 val 的节点也各自需要独立副本。遍历不追随 random，因此 random 中的环不会造成无限递归。

Python 3 · 独立提交

class Solution:
    def copyRandomList(self, head):
        copies = {None: None}
        cur = head
        while cur is not None:
            copies[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur is not None:
            clone = copies[cur]
            clone.next = copies[cur.next]
            clone.random = copies[cur.random]
            cur = cur.next
        return copies[head]

关键代码解释

关键语句	含义与作用
copies = {None: None}	空链、空 random、尾部 next 都能直接查表。
copies[cur.random]	取得旧 random 对象对应的新对象，而非直接保留旧引用。

时间复杂度O(n) 期望时间，两遍遍历，字典平均常量时间访问。

空间复杂度O(n) 辅助映射；此外新结果节点占 O(n)。

选择建议：不改动输入结构，容易审查深拷贝正确性。

解法二：原节点旁交织副本，再拆分

解题思路与正确性

第一遍将 A → B → C 交织成 A → A′ → B → B′ → C → C′。旧节点.next 现在就是它的副本，无需映射表。
第二遍只访问旧节点：若旧 random 指向 R，则副本 random 指向 R.next，也就是 R′。此时所有副本已创建完毕，任意方向都可设置。
第三遍同时恢复原链与抽出副本链。先保存 clone.next 中的下一个旧节点，再设置旧 next 和新 next；返回前原链完整恢复。

Python 3 · 独立提交

class Solution:
    def copyRandomList(self, head):
        if head is None:
            return None
        cur = head
        while cur is not None:
            clone = Node(cur.val)
            clone.next = cur.next
            cur.next = clone
            cur = clone.next
        cur = head
        while cur is not None:
            clone = cur.next
            clone.random = cur.random.next if cur.random is not None else None
            cur = clone.next
        new_head = head.next
        cur = head
        while cur is not None:
            clone = cur.next
            nxt = clone.next
            cur.next = nxt
            clone.next = nxt.next if nxt is not None else None
            cur = nxt
        return new_head

关键代码解释

关键语句	含义与作用
cur.random.next	交织结构使每个旧目标的 next 都是对应副本。
nxt = clone.next	保存下一个旧节点，随后才拆分两条链。
cur.next = nxt	逐个恢复原节点 next；原 random 从未被改动。

时间复杂度O(n)，三遍扫描。

空间复杂度O(1) 辅助空间；新结果节点仍占 O(n)，不能声称存储总量常数。

选择建议：节省映射，但临时修改原链，需能独占操作它；拆分步骤比映射法更易出错。

示例推演

步骤	操作 / 状态	结果 / 不变量
示例约定	[[7,None],[13,0],[11,1]]，第二项为 random 的目标下标	旧节点为 A(7)、B(13)、C(11)
创建副本	A → A′ → B → B′ → C → C′	值相同，对象均不同
设置 random	A′.random=None；B′.random=A′；C′.random=B′	副本指针不接触旧节点
拆分	恢复 A → B → C；抽出 A′ → B′ → C′	random 对应关系保持
输出验证	副本编码仍为 [[7,None],[13,0],[11,1]]	没有任何副本节点与旧节点是同一对象
自指边界	[[1,0]]	新节点 random 指向新节点自身

两种解法对照

解法	时间	辅助空间	取舍
两遍哈希映射（优先掌握）	O(n) 期望时间，两遍遍历，字典平均常量时间访问。	O(n) 辅助映射；此外新结果节点占 O(n)。	不改动输入结构，容易审查深拷贝正确性。
原节点旁交织副本，再拆分	O(n)，三遍扫描。	O(1) 辅助空间；新结果节点仍占 O(n)，不能声称存储总量常数。	节省映射，但临时修改原链，需能独占操作它；拆分步骤比映射法更易出错。

易错点与边界检查

返回 head 或只复制 next 都不是深拷贝；random 也必须指向新节点。
不能按 val 建立字典，相同值节点会冲突。
交织法必须第三遍恢复原链，并处理最后一个 clone.next=None；提交使用平台提供的 Node，不是 ListNode。

15LeetCode 25K 个一组翻转链表

前往 LeetCode 原题 ↗

难度：困难｜核心知识点：分组边界 · 半开区间反转 · 头插法 · 常量空间

题意与边界

把单链表每 k 个节点作为一组反转，不足 k 个的最后一段保持原顺序。只能修改节点连接，不能仅交换 val。原题保证链表长度 1 到 5000，1 ≤ k ≤ 长度；下面也兼容空链。k=1 时结构不变。

满组 [1,2,3] 反转，短尾 [4,5] 保持原序。

解法一：先确认满组，再反转半开区间（推荐）

解题思路与正确性

group_prev 指向上一组尾节点，初始为 dummy。从它出发向后走 k 步得到 kth；若不足 k 个直接返回，确保短尾完全不动。
先保存 group_next = kth.next。反转区间 [group_prev.next, group_next)，把反转中的 prev 初始化为 group_next，让旧组头在反转后自动接回后缀。
反转完成后，kth 成为组新头，旧组头 old_head 成为组尾。让 group_prev.next = kth，再把 group_prev 更新为 old_head，继续处理下一组。

Python 3 · 独立提交

class Solution:
    def reverseKGroup(self, head, k):
        dummy = ListNode(0, head)
        group_prev = dummy
        while True:
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if kth is None:
                    return dummy.next
            group_next = kth.next
            old_head = group_prev.next
            prev, cur = group_next, old_head
            while cur is not group_next:
                nxt = cur.next
                cur.next = prev
                prev, cur = cur, nxt
            group_prev.next = kth
            group_prev = old_head

关键代码解释

关键语句	含义与作用
group_next = kth.next	必须在反转前保存固定边界；kth.next 在反转中会改变。
prev = group_next	反转后旧组头已经接回未处理后缀。
while cur is not group_next	半开区间的右端点不参与反转，用对象身份判断边界。
group_prev = old_head	新的组尾作为下一组前驱，避免再次处理已反转节点。

时间复杂度O(n)，每个满组先定位 k 步再反转 k 步，短尾至多再扫描 k−1 步。

空间复杂度O(1) 辅助空间。

选择建议：局部反转结构清晰，满足进阶；没有递归深度风险。

解法二：统计长度后，每组做 k−1 次头插

解题思路与正确性

先算总长度，只在剩余节点数 ≥ k 时处理。prev 是组前驱，tail 固定指向该组的原头节点。
每次把 tail.next 摘下，插到 prev 后。tail 不动，随着组内头插不断成为反转部分的尾。执行 k−1 次就完成整组逆序。
一组完成后令 prev=tail，剩余长度减 k。短尾不进入循环，所以保持原顺序。此方法不需要每组先找 kth，但增加了一次长度扫描。

Python 3 · 独立提交

class Solution:
    def reverseKGroup(self, head, k):
        length, cur = 0, head
        while cur is not None:
            length += 1
            cur = cur.next
        dummy = ListNode(0, head)
        prev = dummy
        while length >= k:
            tail = prev.next
            for _ in range(k - 1):
                node = tail.next
                tail.next = node.next
                node.next = prev.next
                prev.next = node
            prev = tail
            length -= k
        return dummy.next

关键代码解释

关键语句	含义与作用
tail.next = node.next	先把待搬运节点从原位置摘下。
node.next = prev.next	插到本组当前头之前。
range(k - 1)	k=1 时没有搬运操作，但每轮仍前进并减少长度。

时间复杂度O(n)，长度统计与所有组内搬运次数之和均为线性。

空间复杂度O(1) 辅助空间。

选择建议：与半开区间法同为常量空间；头插过程适合手动画指针，但易把固定 tail 错误向后移动。

示例推演

步骤	操作 / 状态	结果 / 不变量
输入	[1,2,3,4,5]，k=3	group_prev=dummy，kth=3，group_next=4
反转 1	1.next 指向 4	已反转 1 → 4，cur=2
反转 2、3	2.next=1，3.next=2	得到 3 → 2 → 1 → 4 → 5
重连前驱	dummy.next=3，group_prev=1	第一组完成
检查尾段	从 1 后只找到 4、5，不足 3 个	输出 [3,2,1,4,5]
头插对照	先搬 2 到组头，再搬 3 到组头	同样得到 [3,2,1,4,5]；k=2 则为 [2,1,4,3,5]

两种解法对照

解法	时间	辅助空间	取舍
先确认满组，再反转半开区间（推荐）	O(n)，每个满组先定位 k 步再反转 k 步，短尾至多再扫描 k−1 步。	O(1) 辅助空间。	局部反转结构清晰，满足进阶；没有递归深度风险。
统计长度后，每组做 k−1 次头插	O(n)，长度统计与所有组内搬运次数之和均为线性。	O(1) 辅助空间。	与半开区间法同为常量空间；头插过程适合手动画指针，但易把固定 tail 错误向后移动。

易错点与边界检查

先反转再发现不足 k 个，会错误改变短尾；必须先确认边界或计数。
不要在反转过程中动态读取 kth.next 作为终点，因为它已被改写。
组前驱必须更新为旧组头；k=1、k=长度、最后余 1 个节点都应正确。

复盘：从题意选择模板

知识点与选型对照

看到的任务	优先方法	代表题	必须守住的条件
头节点可能被删除或替换	dummy + 前驱	203 / 24 / 19 / 25	返回 dummy.next。
改变链的方向	prev / cur / nxt 三指针	206 / 234 / 25	先存后继；确认反转右边界。
有序序列合并	尾指针归并；K 路选堆或分治	21 / 148 / 23	保持输出前缀有序并挂接余段。
倒数位置	固定间距双指针	19	起点、步数和结束位置成套使用。
中点 / 对称性	快慢分割 + 后半反转	234 / 148	中点模板必须匹配切分位置。
环 / 重复访问	Floyd 判环与入口定位	141 / 142 / 287	第一阶段 1:2，第二阶段 1:1。
两个路径的共同对象	双指针换头	160	无环前提、比较身份、不得改链。
任意引用的深拷贝	映射表或交织副本	138	先创建所有副本，再连接 random。

六个核心模板：记住不变量，再默写完整代码

模板	初始化与关键操作	循环不变量	可复制的完整范例
前驱删除	dummy.next=head；命中则 `prev.next=prev.next.next`，否则 prev 前进。	dummy 到 prev 的真实节点全部保留。	203 解法一
整体 / 区间反转	prev=None（整体）或区间后继（局部）；先存 nxt。	prev 是反转前缀头，cur 是尚未处理头。	206 解法一；25 解法一
结果尾部构造	dummy、tail；接一节点后 tail 前进；最后挂余段。	tail 之前的输出已完成。	21 解法一；2 按位模拟
固定距离	slow=fast=dummy；fast 先走 n+1 步，再同步。	fast 与 slow 相隔 n+1 条边。	19 解法一
Floyd 双阶段	slow=fast=head；1:2 相遇后，一方回头并改为 1:1。	相遇时慢行步数是环长整数倍。	142 解法一；287 的 f(i)=nums[i]
分组边界	确定 kth 和 group_next，保存 old_head 后局部反转。	已完成前缀与未处理后缀均可达。	25 解法一

模板服务于具体约束。第 234 题找中点与第 148 题拆分的 fast 初值和循环条件不同，停止位置也不同；第 19 题固定间距与 Floyd 变速追赶解决的是两类问题。面试时先说出目标停止位置，再写循环条件。

面试前的六个口头检查

这次赋值是在移动指针，还是修改了节点？后缀引用保存在哪里？
头节点会变化吗？使用 dummy 后应当返回哪个引用？
循环结束时 fast、slow、tail、prev 的确切位置是什么？
相同的是数值，还是同一个节点对象？是否需要保持 / 恢复原结构？
我是否把递归栈、堆、字典、输出节点分别算清楚了？
用空链、单节点、重复值、奇数尾部和边界参数手推，是否会越界、漏节点或成环？

掌握程度自测

六天学习计划与间隔复习

天数	练习安排	当天验收
Day 1 · 60–90 分钟	203 → 206 → 21；每题先画图再写代码。	三种指针：前驱、反转前缀头、结果尾；空链与头部变化正确。
Day 2 · 60–90 分钟	复习 206，再练 2 → 24 → 19。	解释 carry、二元组重连、固定间距，闭卷写出边界。
Day 3 · 90 分钟	141 → 142 → 287，单独手推入口证明。	能在纸上画环并说出为什么 finder 从头出发。
Day 4 · 60–90 分钟	160 → 234；复写快慢中点与反转函数。	比较身份与值不混淆；回文测试后结构完全恢复。
Day 5 · 90–120 分钟	148 → 23，比较两种归并策略。	自底向上分段能正确断链，堆相同值不报错。
Day 6 · 90–120 分钟	138 → 25；整专题限时闭卷复盘。	深拷贝对象完全独立；K 组边界与短尾正确。
完成后 +1 / +3 / +7 天	各选 3 题，优先重做没能解释不变量的题。	先讲思路与复杂度，再默写；通过后标记已掌握。

离线使用与代码约定

本文件的 CSS、JavaScript、语法高亮与 SVG 全部内联，无 CDN、字体下载、远程脚本、外部图片或运行时网络请求。代码均为 Python 3 标准库与平台节点类，题目原文链接仅在点击时打开在线站点。题意为教学性转述，题号、难度、约束与链接按力扣对应题目核对。

复制功能优先使用剪贴板 API；本地 file:// 环境不可用时回退到浏览器复制命令，若浏览器仍拒绝，按钮会明确提示手动选择代码。localStorage 不可写时会显示提示，当前页面仍可标记；持久保存需要浏览器允许本地存储。移动或重命名文件、清理浏览器数据、切换浏览器可能使原进度不可见。

打印按钮调用浏览器打印，可另存为 PDF。打印样式隐藏目录与操作按钮、展开所有教学正文，并让长代码折行。建议用浏览器的打印预览确认纸张边距。

LeetCode 链表专题15 道题完整学习手册

学习路线与题目全览

先建立链表的对象模型

统一复杂度口径

空链、单节点、重复值与身份边界

可交互推演：三指针反转

第一阶段 · 指针与基础归并

01LeetCode 203移除链表元素

题意与边界

解法一：虚拟头节点 + 前驱指针（推荐）

解题思路与正确性

关键代码解释

解法二：先处理头部，再删除内部节点

解题思路与正确性

关键代码解释

示例推演

两种解法对照

易错点与边界检查

02LeetCode 206反转链表

题意与边界

解法一：三指针迭代（推荐）

解题思路与正确性

关键代码解释

解法二：递归反转后缀

解题思路与正确性

关键代码解释

示例推演

两种解法对照

易错点与边界检查

03LeetCode 21合并两个有序链表

题意与边界

解法一：双指针迭代归并（推荐）

解题思路与正确性

关键代码解释

解法二：递归选择较小头节点

解题思路与正确性

关键代码解释

示例推演

两种解法对照

易错点与边界检查

第二阶段 · 局部操作与典型应用

04LeetCode 2两数相加

题意与边界

解法：逐位相加并传播 carry

解题思路与正确性

关键代码解释

示例推演

易错点与边界检查

05LeetCode 24两两交换链表中的节点

题意与边界

解法一：dummy + 三条边重连（推荐）

解题思路与正确性

关键代码解释

解法二：递归处理后续二元组

解题思路与正确性

关键代码解释

示例推演

两种解法对照

易错点与边界检查

06LeetCode 19删除链表的倒数第 N 个节点

题意与边界

解法一：保持 n+1 条边的间距（推荐）

解题思路与正确性

关键代码解释

解法二：先统计长度，再定位前驱

解题思路与正确性

关键代码解释

示例推演

两种解法对照

易错点与边界检查

第三阶段 · 快慢指针与环模型

07LeetCode 141环形链表

题意与边界

解法一：快慢指针 Floyd（推荐）

解题思路与正确性

关键代码解释

解法二：哈希集合记录访问节点

解题思路与正确性

关键代码解释

示例推演

LeetCode 链表专题
15 道题完整学习手册