数据结构与算法 / 系统课时

反转单链表

反转单链表

反转单链表的核心不是创建新节点,而是原地改变每个节点的 next 指向。本课将用三个引用完成安全反转,并通过可运行示例验证空链表、单节点和普通链表都能统一处理。

学习目标

  • 理解 prev、current、next_node 的职责与更新顺序
  • 掌握时间复杂度为 O(n)、额外空间复杂度为 O(1) 的迭代实现
  • 能说明为什么修改 current.next 前必须保存原后继

反转过程

设原链表为 1 -> 2 -> 3 -> None。每轮循环先保存当前节点的后继,再把当前节点指向已反转部分,最后同步推进两个边界。

单链表逐节点反转过程

三个引用的职责如下:

  • prev:已反转部分的头节点,初始为 None
  • current:当前待处理节点,初始为 head
  • next_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 中。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

反转单链表

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通