使用递归反转链表

Question

我希望能够编写一个递归函数来反转链表。假设所有元素都已附加到列表中。

我想把head->next->next赋值给head，所以node->next的下一个节点就是节点本身。然后，当递归完成后，将链表的头（this->head）分配给最终节点（head）。

还缺少的是将最后一个节点的 next 分配给 NULL。

这样的东西在任何世界都行得通吗？它给出了 runtime/segmentation 错误。

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 本身的情况。另外，你不能只是 return head...你需要 return reversed 列表的头部。

试试这个：

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;
}

（未测试...）

Answer 2

列表倒序函数必须是尾递归的，否则在对长列表进行递归时会溢出堆栈。例如：

node* reverse(node* n, node* prev = nullptr) {
    if(!n)
        return prev;
    node* next = n->next;
    n->next = prev;
    return reverse(next, n);
}

可以更轻松地内联迭代列表还原：

inline node* reverse(node* n) {
    node* prev = nullptr;
    while(n) {
        node* next = n->next;
        n->next = prev;
        prev = n;
        n = next;
    }
    return prev;
}

使用递归反转链表

Reversing Linked List using Recursion

c++

recursion

reverse

linked-list