🔥个人主页：Milestone-里程碑

❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>

       <<Git>><<MySQL>>

🌟心向往之行必能至

题目描述

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

示例 1：

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

示例 2：

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

---

方法一：双指针迭代法

核心思路

我们用两个指针 prev 和 curr 遍历链表，逐个改变节点的指向：

1. prev 指向当前节点的前一个节点（初始为 nullptr）。
2. curr 指向当前节点（初始为 head）。
3. 每次迭代时，先保存 curr 的下一个节点 next，然后让 curr->next 指向 prev，最后将 prev 和 curr 向前移动。

动画演示

以链表 1 -> 2 -> 3 -> 4 -> 5 为例：

1. 初始：prev = nullptr, curr = 1
2. 保存 next = 2，让 1->next = nullptr，prev = 1, curr = 2
3. 保存 next = 3，让 2->next = 1，prev = 2, curr = 3
4. ... 以此类推，直到 curr 为 nullptr，此时 prev 就是新的头节点。

C++ 代码实现

cpp

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        
        while (curr != nullptr) {
            ListNode* next = curr->next; // 保存下一个节点
            curr->next = prev;           // 反转当前节点的指向
            prev = curr;                 // prev 前进
            curr = next;                 // curr 前进
        }
        return prev; // prev 最终指向新的头节点
    }
};

复杂度分析：

• 时间复杂度：O (n)，n 为链表长度，我们需要遍历整个链表。
• 空间复杂度：O (1)，只使用了常数级的额外空间。

---

方法二：递归法

核心思路

递归的思路是 “化整为零”：

1. 假设链表除头节点外的其余部分已经反转。
2. 只需要处理头节点和已经反转部分的指向关系。
3. 递归的终止条件是链表为空或只有一个节点。

推导过程

以链表 1 -> 2 -> 3 -> 4 -> 5 为例：

1. 递归到最后，head = 5，直接返回 5。
2. 回溯到 head = 4，此时已经反转的子链表是 5。我们需要让 5->next = 4，同时 4->next = nullptr。
3. 回溯到 head = 3，此时已经反转的子链表是 5 -> 4。我们需要让 4->next = 3，同时 3->next = nullptr。
4. ... 以此类推，最终得到 5 -> 4 -> 3 -> 2 -> 1。

C++ 代码实现

cpp

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 递归终止条件
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        
        // 递归反转头节点之后的链表
        ListNode* newHead = reverseList(head->next);
        
        // 处理当前头节点和反转后链表的关系
        head->next->next = head;
        head->next = nullptr;
        
        return newHead;
    }
};

复杂度分析：

• 时间复杂度：O (n)，n 为链表长度，需要递归 n 次。
• 空间复杂度：O (n)，递归调用栈的深度等于链表长度。

---

两种方法对比

方法	时间复杂度	空间复杂度	优点	缺点
双指针迭代	O(n)	O(1)	空间效率高，无栈溢出风险	代码稍长，需要手动维护指针
递归	O(n)	O(n)	代码简洁，逻辑直观	链表过长时可能导致栈溢出

---

总结

反转链表是链表操作的基础，掌握双指针和递归两种方法非常重要：

• 双指针法是面试中更推荐的解法，因为它空间复杂度更低，且避免了递归的栈溢出问题。
• 递归法代码简洁，适合理解链表的分治思想。