专题进阶 · 基础与数据结构推荐总顺序 · 第 26 / 148 课

画出指针更新顺序,理解链表反转、插删条件和哨兵节点。

先学会这些,再进入本课 数组
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 基础与数据结构

链表Linked List

节点通过指针相连;已知前驱时可常数时间插删,随机访问需要逐个遍历。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

画出指针更新顺序,理解链表反转、插删条件和哨兵节点。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

数组中插入一个元素要搬动后续数据。能否改变连接关系而不搬动所有元素?

02一步步得到方法

节点的位置与顺序是两件事

单链表节点保存 value 和 next。内存地址可以分散,逻辑顺序由 next 决定。head 指向首节点,None 表示链尾。下标 5 没有直接地址公式,必须从 head 沿链接走五次。

在已知前驱 prev 的位置插入 x,只需 x.next=prev.next,再 prev.next=x。若只给你一个值而没有节点,寻找位置的 O(n) 工作仍然存在,不能将整个操作宣称为 O(1)。

反转时为什么必须先保存后继

将 current.next 改成 previous 会切断原来的向后链接。因此先 next_node=current.next 保存未处理部分,再反转当前边。接下来 previous 前移到 current,current 前移到 next_node。

循环中始终有两条链:previous 指向已反转的前缀,current 指向未处理后缀。它们覆盖原始节点且没有丢失;这个视角比死记三次赋值更可靠。

头节点为什么常成为特殊情况

删除第一个节点会改变 head,而删除中间节点只改前驱链接。哨兵节点放在真正头节点之前,让所有删除都能拥有前驱,从而统一边界。双向链表额外维护 prev,换取已知节点的常数时间摘除。

03把一个小例子完全算清楚

反转 1 → 2 → 3 → None。

步骤计算与状态为什么这样做
初始previous=None,current=1已处理部分为空
处理 11 → None;current=2先保存 2,避免丢失后缀
处理 22 → 1 → None;current=3把 2 接到已反转前缀
处理 33 → 2 → 1 → Nonecurrent=None,previous 是新头

窄屏可左右滑动表格,阅读完整计算与理由。

同一批节点的链接被反转,没有新建 n 个节点;原来的 head 现在变成链尾。

04为什么这个方法成立

  1. 初始两部分分割成立。
  2. 一次操作从后缀取出首节点,接到前缀头部,因此节点不丢失、不重复。
  3. 后缀为空时,前缀含全部节点且顺序完全反转。

05把推导翻译成代码

Python · 可独立运行的教学实现

class Node:
    def __init__(self, value, next_node=None):
        self.value, self.next = value, next_node

def reverse(head):
    previous, current = None, head
    while current is not None:
        next_node = current.next
        current.next = previous
        previous, current = current, next_node
    return previous

def values(head):
    result = []
    while head is not None:
        result.append(head.value)
        head = head.next
    return result

逐个理解关键决定

next_node = current.next
保存唯一通向未处理后缀的入口,必须在改链接之前。
current.next = previous
只反转这一条边;不要同时猜测后面节点的状态。
return previous
原 head 已不是新链表入口,调用者必须接住返回值。

06时间、空间与实现范围

无环 n 节点链表反转时间 O(n),辅助指针 O(1)。values 为便于观察创建 O(n) 输出列表,不属于反转核心。

链表每节点多一个或两个指针,缓存局部性也通常不如数组;插删优势取决于是否已经定位节点。

07改变条件,检查哪里会出错

先改 next 再寻找原后继

后缀会不可达。严格遵守保存、改边、前移三步。

输入有环却继续用 None 作为唯一停止条件

可能永不结束;本课要求无环,下一节快慢指针解决环检测。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

空链和单节点链反转后是什么?

需要一点提示

跟踪循环是否进入。

查看解析与答案

空链返回 None;单节点 next 仍为 None,返回该节点。

练习 2 · 边界与辨析

知道待删节点但不知道前驱,单链表删除一定 O(1) 吗?

需要一点提示

考虑尾节点。

查看解析与答案

不一定。通常要找前驱;复制后继值的技巧不适用于尾节点,并可能破坏节点身份语义。

练习 3 · 变式与迁移

在 head 前插入值 0,需要移动原节点吗?

需要一点提示

构造新节点的 next。

查看解析与答案

不需要。new=Node(0,head),再令 head=new;只新建一个节点并更新入口。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Python 官方教程 · 数据结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。