C++实现单向链表反转 _ 递归与三指针迭代法对比【源码】-C++-PHP中文网

递归反转链表易栈溢出，因c++默认线程栈仅1~8mb，对应几千级调用深度；链表过长时触发segfault或exception_stack_overflow，且错误堆栈不提示递归过深。

c++实现单向链表反转 _ 递归与三指针迭代法对比【源码】

递归反转链表：为什么容易栈溢出

递归写法简洁，但实际项目中要警惕深度过深导致的 stack overflow。C++ 默认线程栈通常只有 1~8MB，对应约几千级递归调用——一旦链表长度超限（比如读取日志文件构建的链表），程序直接崩溃，且错误堆栈不提示“递归太深”，只报 Segmentation fault 或 EXCEPTION_STACK_OVERFLOW。

递归核心逻辑是「先走到尾节点，再在回退过程中改指针」，必须保证 head->next 非空才递归，否则访问 nullptr->next 会触发未定义行为：

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

if (!head || !head->next) 是终止条件，缺一不可；漏掉 !head 会导致空指针解引用
head->next->next = head 这行依赖上层递归已返回，不能提前执行
没有显式释放原指针，但 C++ 中只要不 new 就无内存泄漏——这点和 Java 不同

三指针迭代法：安全、可控、易调试

真正工程中推荐用三指针（prev、curr、next）迭代，时间 O(n)，空间 O(1)，且每步状态清晰，方便加断点或日志。

关键不是记三个变量名，而是理解「每次只翻转 curr 指向的那一条边」，其余指针只是辅助保活：

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* next = curr->next; // 先存下后继，否则 curr->next 被改后就丢了
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}