单链表反转算法详解：LeetCode 206 题深度解析

🎨 链表反转的艺术

🧠 算法思路图解

原始链表

1 --> 2 --> 3 --> 4 --> 5 --> NULL

反转过程

NULL <-- 1 2 --> 3 --> 4 --> 5

NULL <-- 1 <-- 2 3 --> 4 --> 5

NULL <-- 1 <-- 2 <-- 3 4 --> 5

NULL <-- 1 <-- 2 <-- 3 <-- 4 5

NULL <-- 1 <-- 2 <-- 3 <-- 4 <-- 5

图表说明：展示了链表从原始状态逐步被反转的全过程，每一步都清晰地显示了已反转部分和未反转部分的分界

🔍 核心思想三指针法

反转链表的核心在于三指针技巧，这就像三位默契的舞伴，各司其职又相互配合：

1. Pre 指针：始终指向已反转部分的头节点，初始为 NULL
2. Current 指针：指向待反转部分的头节点，初始为原链表头
3. Next 指针：临时保存 current 的下一个节点，防止链表断裂

💻 代码实现详解

下面让我们用 C++ 来实现这一优雅的算法：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 边界条件处理：空链表或单节点链表直接返回
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* pre = nullptr;       // 已反转部分的头节点
        ListNode* current = head;      // 待反转部分的头节点
        ListNode* p = nullptr;         // 临时指针
        while (current != nullptr) {
            p = current->next;         // 保存下一个节点
            current->next = pre;       // 反转当前节点
            pre = current;             // pre 前移
            current = p;               // current 前移
        }
        return pre;                    // 最终 pre 就是新链表的头节点
    }
};

📝 代码关键点解析

1. 边界处理：首先检查链表是否为空或只有一个节点，这些情况无需反转
2. 指针初始化：三个指针各就各位，准备开始'舞蹈'
3. 循环反转：每一步都精心安排三个指针的移动，确保链表不会断裂
4. 返回值：最终 pre 指针指向的就是反转后的新链表头

🏆 性能分析

让我们用表格来清晰展示算法的性能表现：

指标	数值/描述	说明
时间复杂度	O(n)	只需遍历链表一次
空间复杂度	O(1)	只使用了固定数量的指针变量
稳定性	稳定	不改变相同值节点的相对顺序
适用性	单链表	不适用于双向链表等复杂结构

🌈 变式与扩展

掌握了基础的反转方法后，我们可以挑战一些有趣的变式问题：

1. 反转链表的一部分（LeetCode 92 题）
2. K 个一组反转链表（LeetCode 25 题）
3. 回文链表判断（LeetCode 234 题）

💡 总结与思考

链表反转看似简单，却蕴含着指针操作的深刻原理。通过三指针的优雅舞蹈，我们实现了链表的完美转身。记住：

• 始终明确每个指针的职责
• 注意保存下一个节点的引用，防止链表断裂
• 边界条件的处理同样重要