反转链表

Question

我正在尝试反转链表并将其保存到另一个新的喜欢的列表中并删除旧的，但是在编译时出现错误..这是函数..

LinkedList LinkedList::reverse(){
    LinkedList L2;
    Node * temp=head;
    while(temp->next!=NULL){
        Node * del=NULL;
        L2.addAtFront(temp->data);
        del=temp;
        temp=temp->next;
        delete del;
     }
     return L2;

}

Answer 1

当（且仅当）您不再需要原始链表时使用它！

而不是使用更便宜的addAtFront（因为你需要为新节点分配内存并销毁旧节点），你可以重用节点和LinkedList（毕竟，您要删除原来的，然后简单地设置指针：

LinkedList LinkedList::reverse(){
    Node* na = head;
    Node* nb = NULL;
    Node* nc = NULL;
    if(na == NULL) {
        return this;
    }
    nb = na->next;
    na->next = NULL;
    while(nb != NULL){
        nc = nb->next;
        nb->next = na;
        na = nb;
        nb = nc;
    }
    tail = head; //if you keep a tail?
    head = na;
    return this;
}

该方法的工作原理如下，您扫描原始列表并使用三个引用：na、nb 和 nc。谁按原名单顺序排列。

现在你肯定知道 na 和 nb 在 while 循环中是有效的。您首先要确保将 nb 的下一个引用存储在 nc 中。接下来你把nb的->next设置为na（原来na->next是nb），所以现在反过来了。

然后你在这个过程中转变：na变成旧的nb，nb变成旧的nc。你一直重复这个直到你到达链表的末尾。

您需要完成两项额外任务： - 将原来的head的->next设置为null，否则会构造循环；和 - 将原来LinkedList的尾部设置为head.

如果维护一个tail，首先需要将它设置为head。

反转链表

Reverse a LinkedList

c++

reverse

linked-list