递归反转链表出现Segmentation Fault的原因排查

问题描述 #

尝试用递归方法反转链表，触发Segmentation Fault（段错误）。C++代码如下：

#include <iostream>

class node {
public:
    int data;
    node* next;

    node(int val) : data(val) {
        this->next = nullptr;
    }
};

class linkedlist {
public:
    node* head;

    linkedlist() {
        this->head = nullptr;
    }

    void print() {
        while(head != nullptr) {
            std::cout << head->data << " ";
            head = head->next;
        }
    }

    void push(int val) {

        if (head == nullptr) {
            head = new node(val);
            return;
        }
        node* temp = new node(val);
        temp->next = head;
        head = temp;
    }

    // node* recursive_reverse(node* head) {
    //     if (head == nullptr || head->next == nullptr) return head;
    //     node* _rest = recursive_reverse(head->next);
    //     head->next->next = head;
    //     head->next = nullptr;
    //     head = _rest;
    //     return head;
    // }


    node* rr_bourne_again(node* head) {
        if (head->next == nullptr) return head;
        node* temp = new node(0);
        temp->next = head;
        head = temp;
        node* _rest = rr_bourne_again(head->next);
        head->next->next = nullptr;
        head = _rest;
        delete(temp);
        temp = nullptr;
        return head;
    }
};

int main()
{
    linkedlist ll;
    for (int i = 10; i > 0; i--) ll.push(i);

    // ll.head = ll.recursive_reverse(ll.head);
    
    ll.head = ll.rr_bourne_again(ll.head);
    ll.print();
}

实现思路：在链表头部添加一个临时节点作为新头，将链表拆分为新头节点和原链表两部分，反转剩余链表后将其指向nullptr，最后释放临时节点的内存。

期望输出：10 9 8 7 6 5 4 3 2 1，实际触发段错误。

错误原因分析 #

• 无限递归导致栈溢出：在rr_bourne_again函数中，创建临时节点temp后将head指向temp，随后递归调用rr_bourne_again(head->next)——而head->next就是最初传入该函数的原链表节点，这导致每次递归传入的都是同一个节点，永远无法触发终止条件，最终栈溢出触发段错误。
• 未处理空指针情况：函数开头的终止条件if (head->next == nullptr)未判断head本身是否为nullptr，若传入空链表，直接访问head->next会立即触发空指针访问错误。
• 反转逻辑错误：代码仅将当前节点的next设为nullptr，未将反转后的链表与当前节点建立正确连接，即使递归终止，最终也只能得到原链表的最后一个节点，前面的节点全部丢失。

修复方案 #

你注释掉的recursive_reverse函数是正确的递归反转实现，直接启用即可解决问题。该函数的核心逻辑是：

1. 终止条件：链表为空或只有一个节点时直接返回
2. 递归反转剩余链表
3. 将当前节点挂到反转后链表的末尾
4. 更新头节点为反转后的链表头

修复后的main函数调用正确的反转函数即可：

int main()
{
    linkedlist ll;
    for (int i = 10; i > 0; i--) ll.push(i);

    ll.head = ll.recursive_reverse(ll.head);
    
    // ll.head = ll.rr_bourne_again(ll.head);
    ll.print();
}

内容的提问来源于stack exchange，提问作者Mccranky83