单链表反转算法详解：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 前移
        }
         pre;                    
    }
};