交换链表的最后一个节点将进入无限期——C++

Question

下面是代码，

#include<bits/stdc++.h>
using namespace std;

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

    node(){
        this->next = NULL;
    }

    node(int data){
        this->data = data;
        this->next = NULL;
    }
};

class linkedList{
public:
    node * head;
    node * tail;

    linkedList(){
        this->head = NULL;
    }

    void getTail(node *& t){
        t = head;
        while(t->next != NULL){
            t = t->next;
        }
    }

    void insertAtEnd(int data){
        node * newNode = new node(data);

        if(head == NULL){
            head = newNode;
            return;
        }

        node * temp = head;
        while(temp->next != NULL){
            temp = temp->next;
        }
        temp->next = newNode;
    }

    void print(){
        node * temp = head;
        while(temp != NULL){
            printf("%d->", temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }

    void swap(node *& a, node *& b){ 
        node * temp = a;
        a = b;
        b = temp; 
    } 

    void swapNode(node ** start, node ** end){
        swap(*start, *end);
        swap(((*start)->next), (*end)->next);
    }
};

int main(){
    ///////////////////////////////////////
    linkedList * ll1 = new linkedList(); //
    ll1->insertAtEnd(6);                 //
    ll1->insertAtEnd(2);                 //
    ll1->insertAtEnd(1);                 //
    ll1->insertAtEnd(3);                 //
    ll1->print();                        /////////////////////
    ll1->swapNode(&ll1->head, &ll1->head->next->next->next);// ----> This is working
    //////////////////////////////////////////////////////////

    linkedList * ll2 = new linkedList();
    ll2->insertAtEnd(6);
    ll2->insertAtEnd(2);
    ll2->insertAtEnd(1);
    ll2->insertAtEnd(3);
    ll2->print();
    node * tail;
    ll2->getTail(tail);
    ll2->swapNode(&ll2->head, &tail); // This is not working // Going into a infinte loop
    ll2->print();

}

当尾节点存储在某个其他变量中时，似乎有一个永远的循环。当通过使用 next 指针遍历到 last 给出尾节点时，代码正在运行。

因此，下面是链表第一个示例的输出，即 6->2->1->3->空 1->2->6->3->NULL

对于链表#2，输出是这样的 6->2->1->3->空 3->2->1->3->2->1->3->2->1->3->2->1->3->2->1->3->2- >1->3->2->1->3->2->1->3->2->1->3->2->1->3->2->1->3 ->2->1->3->2->1->3->2->1->3->2->1->3->2->1->3->2-> 1->3->2->1->3->2->1->3->2->1->3->2->1->3->2->1->3- >2->1->3->2->1->3->2->1->3->2->1->3->2->1->3->2->1 ->3->2->1->3->2->1->3->2->1->3->2->1->3->2->1->3-> 2->1->3->2->1->3->2->1->3->2->1->3->2->1->3->2->1- >3->2->1->3->2->1->3->2->1->3->2->1->3->2->1->3->2 ->1->3->2->1->3->2->1->3->2->1->3->2->1->3->2->1-> 3->2->1->3->2->1->3->2->1->3->2->1->3->2->1->3->2- >1->3->2->1->3->2->1->3->2->1->3->2->1->3->2->1->3 ->2->1->3->2->1->3->2->1->3->2->1->3->2->1->3->2-> 1->3->2->1->3->2->1->3->2->1->3->2->1->3->2->1->3- >2->1->3->2->没有结局

Answer 1

当您交换两个节点 a 和 b 时，您还必须修复到达 a 和到达 b 的指针。例如

     x1 -> x2 -> a -> x3 -> x4 -> b -> x5 -> x6 -> NULL

交换节点 a 和 b 不需要只修复 a.next 和 b.next，也不需要修复 x2.next 和 x4.next.

您的实施中缺少该部分代码。

Answer 2

在处理链表时，图片通常很有帮助。这是首发名单。

head
 |
 V
 ------------    ------------    ------------    ------------    
 | 6 | next | -> | 2 | next | -> | 1 | next | -> | 3 | NULL |
 ------------    ------------    ------------    ------------

现在调用ll1->swapNode(&ll1->head, &ll1->head->next->next->next)，为图片添加两个变量

start
  |
  V
  head                                  end
   |                                     |
   V                                     V
   ------------    ------------    ------------    ------------    
   | 6 | next | -> | 2 | next | -> | 1 | next | -> | 3 | NULL |
   ------------    ------------    ------------    ------------

接下来是对swap(*start, *end)的调用，它交换数据为1的节点中的头指针和next指针。所以head指针会指向3节点，而1节点会指向6节点。

                                              start
                                                |
                                                V
                                      end       head
                                       |         |
                                       V         V
 ------------    ------------    ------------    ------------    
 | 6 | next | -> | 2 | next | -> | 1 | next |    | 3 | NULL |
 ------------    ------------    ------------    ------------    
 ^                                      |
 |                                      |
 L---------------------------------------

最后，调用swap(((*start)->next), (*end)->next)，它交换数据为3和6的节点中的next指针。所以 3 节点将指向 2 节点，而 6 节点的指针将变为空。

       start
         |
         V
         head
          |
          V
          ------------
          | 3 | next |
          ------------                end
                 |                     |
                 V                     V
 ------------    ------------    ------------
 | 6 | NULL |    | 2 | next | -> | 1 | next |
 ------------    ------------    ------------
 ^                                      |
 |                                      |
 L---------------------------------------

万岁！节点已交换。

现在看调用ll2->swapNode(&ll2->head, &tail);，在初始图片上增加了三个变量

start                                            end
  |                                               |
  V                                               V
  head                                            tail
   |                                               |
   V                                               V
   ------------    ------------    ------------    ------------    
   | 6 | next | -> | 2 | next | -> | 1 | next | -> | 3 | NULL |
   ------------    ------------    ------------    ------------

接下来是对swap(*start, *end)的调用，它交换头指针和tail（不是列表的尾指针，而是main()的局部变量）。

 end                                            start
  |                                               |
  V                                               V
  tail                                            head
   |                                               |
   V                                               V
   ------------    ------------    ------------    ------------    
   | 6 | next | -> | 2 | next | -> | 1 | next | -> | 3 | NULL |
   ------------    ------------    ------------    ------------

与第一种情况已经有明显的区别，因为列表的节点没有改变。嗯……好吧，让我们继续调用swap(((*start)->next), (*end)->next)，它交换数据为3和6的节点中的next指针。因此 3 节点将指向 2 节点，而 6 节点的指针将变为空。 第一种情况是这样的，这样会好吗？

 end                                            start
  |                                               |
  V                                               V
  tail                                            head
   |                                               |
   V                                               V
   ------------    ------------    ------------    ------------    
   | 6 | NULL |    | 2 | next | -> | 1 | next | -> | 3 | next |
   ------------    ------------    ------------    ------------    
                   ^                                      |
                   |                                      |
                   L---------------------------------------

问题！我们剩下一个循环！将 1 节点更改为指向 6 节点的步骤发生了什么？没错，我们改成了tail，结果就惨了

我会推荐三件主要的事情来将您的代码移动到更强大的基础上。（也就是说，不要尝试修复当前的错误。先做这些，因为它们会改变竞争环境。）

干掉#include<bits/stdc++.h>；而是包含您需要的 headers 。对于此示例，您只需要 #include <cstdio>.
使 node 成为 linkedList 的 private 实现细节。鲁棒性往往会随着封装而增加。如果没有人知道 linkedList 使用的数据结构，您就限制了其他代码可以做的事情。由于要考虑的可能性越少，就越容易确保您考虑了所有这些可能性。
不要声明从未使用过的字段 (linkedList::tail)。有人会想在某个时候使用该字段而没有意识到它包含垃圾。

（还有其他的改进，我认为这三个是最重要的。）

交换链表的最后一个节点将进入无限期——C++

Swapping last node of the linked list is going into a infinte -- C++

c++

pointers

linked-list

data-structures

singly-linked-list