跳到主要内容

206. 反转链表

题目描述​

给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

示例​

示例 1：

输入: head = [1,2,3,4,5]
输出: [5,4,3,2,1]

示例 2：

输入: head = [1,2]
输出: [2,1]

示例 3：

输入: head = []
输出: []

解题思路​

第一步：理解问题本质​

反转链表意味着：

  • 原来的头节点变成尾节点
  • 原来的尾节点变成头节点
  • 每个节点的 next 指针指向前一个节点而不是后一个

第二步：暴力解法 - 使用栈​

遍历链表，将所有节点值存入栈，然后创建新链表。

# 先把所有值按顺序压栈，再逐个弹出重建，借栈实现「后进先出」的倒序
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    stack = []
    cur = head
    # 一路走到链表末尾，值依次入栈，最后一个值位于栈顶
    while cur:
        stack.append(cur.val)
        cur = cur.next

    # 哑节点统一「往尾部接新节点」的写法，省掉第一个节点的特判
    dummy = ListNode(0)
    cur = dummy
    # 出栈顺序正好与原链表相反，接出来的新链表就是反转结果
    while stack:
        cur.next = ListNode(stack.pop())
        cur = cur.next

    # dummy 本身不是结果，真正的头是它的下一个节点
    return dummy.next

为什么不够好：需要 O(n) 额外空间，且创建了新节点而非原地反转。

第三步：优化解法 - 递归​

递归到链表末尾，返回时反转指针。

# 递归到链表末尾，再把指针一层层掉头
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # 递归出口：空链表或只有一个节点，反转后还是它自己
    if not head or not head.next:
        return head

    # 先让子链表彻底反转，拿回新的头节点（原链表的尾节点）
    new_head = self.reverseList(head.next)
    # 让原来的后一个节点指回当前节点，这一段的指针就掉头了
    head.next.next = head
    # head 现在是新链表的尾节点，必须断开原来的后继，否则首尾相连成环
    head.next = None

    # 整条链已经反转完，新头节点一直向上传递
    return new_head

分析：时间 O(n)，空间 O(n)（递归栈）。

第四步：最优解法 - 迭代（三指针法）​

使用三个指针：pre、cur、nxt，遍历链表时逐个反转指针方向。

完整代码实现​

算法可视化 · 逐帧回放这道题的代码6 帧 · 录制输入 [1,2,3,4,5]
from typing import Optional

class Solution:
    """
    反转链表 - 迭代法

    核心思路：
    使用三个指针：pre（前一个节点）、cur（当前节点）、nxt（下一个节点）
    遍历链表，每次将 cur.next 指向 pre，实现局部反转

    时间复杂度：O(n)
    空间复杂度：O(1)
    """

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # pre: 前一个节点（已反转部分的头节点）
        # cur: 当前处理的节点
        pre = None
        cur = head

        while cur:
            # 保存下一个节点，防止断链后找不到
            nxt = cur.next

            # 反转：将当前节点的 next 指向前一个节点
            cur.next = pre

            # 移动指针
            pre = cur
            cur = nxt

        return pre

示例推演​

以 [1,2,3,4,5] 为例：

初始状态：

pre: None
cur: 1 -> 2 -> 3 -> 4 -> 5 -> None

第1轮：

nxt = 2
cur.next = pre = None
pre = 1 -> None
cur = 2 -> 3 -> 4 -> 5 -> None

第2轮：

nxt = 3
cur.next = pre = 1 -> None
pre = 2 -> 1 -> None
cur = 3 -> 4 -> 5 -> None

第3轮：

nxt = 4
cur.next = pre = 2 -> 1 -> None
pre = 3 -> 2 -> 1 -> None
cur = 4 -> 5 -> None

第4轮：

nxt = 5
cur.next = pre = 3 -> 2 -> 1 -> None
pre = 4 -> 3 -> 2 -> 1 -> None
cur = 5 -> None

第5轮：

nxt = None
cur.next = pre = 4 -> 3 -> 2 -> 1 -> None
pre = 5 -> 4 -> 3 -> 2 -> 1 -> None
cur = None

结束：cur 为 None，返回 pre = [5,4,3,2,1]

复杂度分析​

解法时间复杂度空间复杂度说明
栈O(n)O(n)需要额外栈空间
递归O(n)O(n)递归栈空间
迭代（三指针）O(n)O(1)最优解法

易错点总结​

1. 忘记保存 next 指针​

错误：

# 顺序反了：还没保存后继就改 next，后面整条链再也找不回来
cur.next = pre   # 断链了！
cur = cur.next   # 错误！cur.next 已经是 pre 了

正确：

# 先存后退：nxt 必须在 cur.next 被改写之前拿到
nxt = cur.next   # 先保存
cur.next = pre   # 再反转
cur = nxt        # 移动到保存的 next

2. 返回错误的节点​

错误：return cur（cur 最后是 None）

正确：return pre（pre 指向新的头节点）

3. 递归法忘记断开原指针​

# 让后一个节点指回当前节点，就完成了这一段的掉头
head.next.next = head
# 当前节点成为新的尾节点，next 必须置空，否则两端互指形成环
head.next = None  # 必须断开，否则形成环

扩展思考​

1. 反转指定区间的链表​

92. 反转链表 II：反转从位置 m 到 n 的链表。

2. K 个一组反转链表​

25. K 个一组翻转链表：每 k 个节点反转一次。

3. 相关题目​

相关题目​

自测​

加载评论中...