使用递归反向链表

Question

还缺少的是将最后一个节点的next赋值为NULL。

在任何世界里，像这样的东西会起作用吗？它给出了一个运行时/分段错误。

struct node {
    int data;
    node *next;
};

class LinkedList{
    node *head = nullptr;
public:
    node *reverse(node *head){
        if(head->next != nullptr){
            reverse(head->next)->next = head;
        }
        else{
            this->head = head;
        }
        return head;
    }
};

Answer 1

注意，您忽略了head是nullptr本身的情况。此外，您不能只返回head······您需要返回反向列表的头部。

试试这个：

node* reverse_list(node* head) {
    if (head == nullptr or head->next == nullptr) { return head; }
    auto tail = head->next;
    auto reversed_tail = reverse_list(tail);
    // tail now points to the _last_ node in reversed_tail,
    // so tail->next must be null; tail can't be null itself        
    tail->next = head; 
    head->next = nullptr;
    return reversed_tail;
}

（未测试……)