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 | 已处理部分为空 |
| 处理 1 | 1 → None;current=2 | 先保存 2,避免丢失后缀 |
| 处理 2 | 2 → 1 → None;current=3 | 把 2 接到已反转前缀 |
| 处理 3 | 3 → 2 → 1 → None | current=None,previous 是新头 |
窄屏可左右滑动表格,阅读完整计算与理由。
同一批节点的链接被反转,没有新建 n 个节点;原来的 head 现在变成链尾。
04为什么这个方法成立
- 初始两部分分割成立。
- 一次操作从后缀取出首节点,接到前缀头部,因此节点不丢失、不重复。
- 后缀为空时,前缀含全部节点且顺序完全反转。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
空链和单节点链反转后是什么?
需要一点提示
跟踪循环是否进入。
查看解析与答案
空链返回 None;单节点 next 仍为 None,返回该节点。
知道待删节点但不知道前驱,单链表删除一定 O(1) 吗?
需要一点提示
考虑尾节点。
查看解析与答案
不一定。通常要找前驱;复制后继值的技巧不适用于尾节点,并可能破坏节点身份语义。
在 head 前插入值 0,需要移动原节点吗?
需要一点提示
构造新节点的 next。
查看解析与答案
不需要。new=Node(0,head),再令 head=new;只新建一个节点并更新入口。