17370845950

三指针迭代法是原地反转单链表最常用解法，空间复杂度O(1)，核心是用prev、curr、next避免链表断裂；递归法简洁但有栈溢出风险；使用std::list应调用其reverse()成员函数，手写单链表无此接口；反转前须检测环，否则行为未定义。

用三指针迭代法原地反转单链表

这是最常用、空间复杂度为 O(1) 的解法，核心是维护 prev、curr、next 三个指针，逐步将每个节点的 next 指向前一个节点。

常见错误是忘记在修改 curr->next 前保存下一个节点，导致链表断裂：

Node* reverseList(Node* head) {
    Node* prev = nullptr;
    Node* curr = head;
    while (curr != nullptr) {
        Node* next = curr->next;  // 必须先存下，否则 curr->next 被改写后就找不到了
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;  // 新头结点
}

• prev 初始为 nullptr，对应反转后尾节点的 next
• 循环结束时 curr 为 nullptr，prev 恰好指向原链表尾、新链表头
• 空链表（head == nullptr）和单节点链表可自然处理，无需特判

递归实现要注意栈深度和边界返回值

递归写法简洁但隐含 O(n) 栈空间开销，且对超长链表易触发栈溢出。关键在于：递归调用必须返回新链表的头，而原地修改发生在回溯过程中。

Node* reverseList(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;  // 递归终止：空链或单节点，直接返回自身（即新头）
    }
    Node* newHead = reverseList(head->next);  // 先翻转后续部分
    head->next->next = head;                 // 让原下一个节点指向自己
    head->next = nullptr;                    // 自己变成尾，next 置空
    return newHead;
}

• 必须在 reverseList(head->next) 后立刻用 head->next->next，不能用临时变量缓存再操作，否则逻辑错乱
• 最后一行 head->next = nullptr 不可省略，否则会留下环（如 1→2→1）
• 调试时可加日志观察递归深度，gdb 中容易因栈帧过多中断

使用 std::list 时别误用 reverse() 成员函数

如果项目中本就用的是 std::list（双向链表），直接调 reverse() 最安全高效；但若底层是手写单向链表，千万别试图调用同名函数——它不存在。

立即学习“C++免费学习笔记（深入）”；

• std::list lst = {1,2,3}; lst.reverse(); ✅ 有效，O(n) 时间
• Node* 类型没有 reverse() 成员函数 ❌ 编译报错：error: 'reverse' is not a member of 'Node'
• 混淆根源常是文档看混了：STL 容器接口 ≠ 手写链表接口

测试时漏掉环形链表会导致无限循环

反转前未检测环，反转后可能形成自环或死循环，尤其在面试手撕或单元测试中容易被忽略。

• 简单检测可用快慢指针：hasCycle(head)，在 reverseList() 调用前加断言
• 反转后若原链表有环，新链表结构不可预测，行为未定义
• 用 valgrind --tool=memcheck 运行可暴露非法内存访问，但无法直接报环

真正麻烦的不是算法本身，而是把反转嵌在更大逻辑里时——比如在 LRU 缓存淘汰路径中翻转某段链表，却没确认该段是否独立、无环、无并发访问。