数据结构与算法 / 系统课时
反转单链表
反转单链表
反转单链表的核心不是创建新节点,而是原地改变每个节点的 next 指向。本课将用三个引用完成安全反转,并通过可运行示例验证空链表、单节点和普通链表都能统一处理。
学习目标
- 理解
prev、current、next_node的职责与更新顺序 - 掌握时间复杂度为 O(n)、额外空间复杂度为 O(1) 的迭代实现
- 能说明为什么修改
current.next前必须保存原后继
反转过程
设原链表为 1 -> 2 -> 3 -> None。每轮循环先保存当前节点的后继,再把当前节点指向已反转部分,最后同步推进两个边界。

三个引用的职责如下:
prev:已反转部分的头节点,初始为Nonecurrent:当前待处理节点,初始为headnext_node:临时保存未处理部分的入口
下面是循环体的片段示例,依赖已定义的 prev、current 和 next_node:
python
next_node = current.next
current.next = prev
prev = current
current = next_node第一行如果省略,第二行执行后就无法再找到原来的后继节点。
主示例
下面的程序包含节点定义、链表构造、反转和结果转换,可直接运行。
python
from dataclasses import dataclass
from typing import Optional
@dataclass
class ListNode:
value: int
next: Optional["ListNode"] = None
def from_list(values: list[int]) -> Optional[ListNode]:
# 虚拟头节点统一空输入和首次插入的处理
dummy = ListNode(0)
tail = dummy
for value in values:
node = ListNode(value)
tail.next = node
tail = node
return dummy.next
def reverse(head: Optional[ListNode]) -> Optional[ListNode]:
prev: Optional[ListNode] = None
current = head
while current is not None:
# 每轮把一个节点从未处理部分移动到已反转部分
# 先保留未处理链表入口,再修改 current.next
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
def to_list(head: Optional[ListNode]) -> list[int]:
result: list[int] = []
current = head
while current is not None:
result.append(current.value)
current = current.next
return result
def main() -> None:
for values in ([], [1], [1, 2, 3, 4, 5]):
head = from_list(values)
print(values, "->", to_list(reverse(head)))
if __name__ == "__main__":
main()运行命令:
bash
python reverse_linked_list.py预期输出:
text
[] -> []
[1] -> [1]
[1, 2, 3, 4, 5] -> [5, 4, 3, 2, 1]正确性与边界
循环开始时,prev 可达的节点已经反转,current 可达的节点仍保持原顺序,两部分合起来恰好是原链表的全部节点。每轮只把一个节点从未处理部分移动到已反转部分,因此不会重复或遗漏。
空链表不会进入循环,直接返回 None;单节点链表执行一轮后仍指向 None。反转完成后,原头节点成为尾节点,新的入口必须使用函数返回值保存。
最常见的错误是先执行 current.next = prev,再尝试通过 current.next 前进,此时该引用已经指向旧前驱。另一个错误是返回 current,但循环结束时它必定为 None,正确结果保存在 prev 中。
按自己的节奏,确认真正理解。