题目

力扣题目

给定单链表的头节点 head，反转链表并返回反转后的头节点。可以使用迭代或递归方式实现。

示例 1：

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

示例 2：

Text
输入：head = [1,2]
输出：[2,1]

示例 3：

Text
输入：head = []
输出：[]

考察内容

  • 单链表指针方向修改
  • 保存后继节点
  • 已反转与未反转区间
  • 迭代状态转移
  • 递归回溯

解题思路

迭代法

使用三个指针：

  • prev：已反转部分的头节点；
  • cur：当前准备处理的节点；
  • next：临时保存原链表中 cur 的后继。

每轮执行四步：

Text
next = cur->next       保存后继
cur->next = prev       反转当前指针
prev = cur             已反转部分向前扩展
cur = next             继续处理原后继

保存 next 必须发生在修改 cur->next 之前，否则原链表剩余部分的入口会丢失。

循环过程中维护的不变量是：

  • prev 指向已经完成反转的链表；
  • cur 指向尚未处理部分的第一个节点；
  • 两部分包含原链表的全部节点且不重不漏。

当 cur == nullptr 时，所有节点均已反转，prev 就是新的头节点。

⤢ 打开

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

递归法

递归反转 head->next 开始的子链表，得到新头节点 newHead。回溯时执行：

Text
head->next->next = head
head->next = nullptr

第一句让原后继指回当前节点，第二句断开原来的正向连接，避免形成环。递归时间复杂度为 O(n)O(n)，调用栈空间为 O(n)O(n)。

代码演示

C++
struct ListNode {
    int val;
    ListNode* next;

    explicit ListNode(int value = 0, ListNode* nextNode = nullptr)
        : val(value), next(nextNode) {}
};

// 迭代写法：推荐掌握
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* cur = head;

    while (cur != nullptr) {
        ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }

    return prev;
}

// 递归写法
ListNode* reverseListRecursive(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }

    ListNode* newHead = reverseListRecursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

易错点

  • 修改指针前没有保存后继：执行 cur->next = prev 后将无法通过 cur 找到原来的下一节点。
  • 返回 cur：循环结束时 cur == nullptr，新头节点是 prev。
  • prev 未初始化为空指针：原头节点反转后应成为尾节点，其 next 必须指向 nullptr。
  • 只交换节点值：题目要求反转链表结构，应修改节点连接关系。
  • 递归时忘记断开 head->next：会形成双向连接或环。
  • 空链表和单节点链表：迭代写法自然处理；递归写法必须设置基线条件。

总结

反转链表的关键是先保存原后继，再改变当前节点的指向。迭代法把链表分成“已反转”和“待处理”两部分，每轮移动边界；递归法则在回溯阶段反转每一条边。

相关题目

    1. 两两交换链表中的节点
    1. 反转链表 II
    1. 移除链表元素
    1. 回文链表
    1. K 个一组翻转链表