使用递归反向链表

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (44)

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

我想分配Head->Next->HEAD旁边,所以节点的下一个节点->Next是节点本身。然后,当递归完成时,将链接列表的头(this->head)分配给最后一个节点(即head)。

还缺少的是将最后一个节点的旁边分配为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;
    }
};
提问于
用户回答回答于

注意,你忽略了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;
}
用户回答回答于

列表反转函数必须是尾递归的,否则当在长列表上递归时,它会使堆栈溢出。例如:

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

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动