17370845950

就地反转单链表必须用三指针轮换（prev、curr、next），在一次遍历中完成next重定向，时间O(n)、空间O(1)；头插法因新建节点不满足原地要求，会导致空间复杂度超标和内存隐患。

就地反转单链表，核心是三个指针轮换：prev、curr、next，边遍历边改指针方向，时间 O(n)，空间 O(1)——考研代码题里必须写对，错一个指针赋值顺序就全崩。

为什么不能直接遍历后头插？

头插法看似简单，但本质是「新建链表」，不是就地反转。考研明确要求「原地」（in-place），即只调整现有节点的 next 指针，不 new 新节点、不额外开数组。否则判为逻辑错误或空间复杂度超标（O(n) vs O(1)）。

• 头插法会隐式改变节点物理顺序，且若链表含自定义析构逻辑，new/delete 不匹配可能引发内存问题
• 面试/机试中若用头插却没声明“非就地”，会被追问空间代价，容易失分
• 真正就地反转必须在一次遍历中完成所有 next 重定向

reverseList 函数的标准三指针写法

以 LeetCode 206 和《王道数据结构》风格为准，假设节点定义为：

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
};

关键在于 next 的保存时机和赋值顺序：

• 先用临时变量 next 保存 curr->next，否则改完 curr->next 后就断链了
• 再执行 curr->next = prev，把当前节点指向前驱
• 最后更新 prev = curr、curr = next，推进迭代
• 循环结束时 curr 为 nullptr，prev 恰好指向新头节点

完整函数：

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* next = curr->next;  // 必须在改 curr->next 前保存
        curr->next = prev;            // 反转当前边
        prev = curr;                  // prev 前进
        curr = next;                  // curr 前进
    }
    return prev;  // 新头节点
}

容易丢分的边界与细节

考研代码题常卡在这些地方，不是算法不会，而是实现毛糙：

• head 为 nullptr 时，while 不进循环，直接返回 prev（即 nullptr），正确——无需单独 if 判断
• 不要写成 curr->next = prev; prev = curr; curr = curr->next;，这里 curr->next 已被修改，curr = curr->next 会跳到错误位置甚至

  

  野指针
• 若题目要求返回「反转后尾节点」（少见但有），注意原头节点的 next 已置为 nullptr，它就是新尾，别误以为要遍历找
• C++ 中指针未初始化（如漏写 ListNode* prev = nullptr）会导致 undefined behavior，务必显式初始化

真正难的不是思路，是写三行指针操作时不手抖——多练几次，把 next 保存那句刻进肌肉记忆，就稳了。