c++ - 交换链表的最后一个节点将变成无限个-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();

}

当尾节点存储在其他变量中时，似乎存在一个永远的循环。
当代码工作时，使用下一个指针遍历最后一个末尾节点即可给出尾节点。

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

对于链接列表2，输出如下所示
6-> 2-> 1-> 3-> NULL
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

图片在处理链接列表时通常会有所帮助。这是开始列表。

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)的调用，该调用在数据为 next的节点中交换头指针和 1指针。因此，头指针将指向 3节点，而 1节点将指向 6节点。

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

最后，调用 swap(((*start)->next), (*end)->next)，该调用将在数据为 next和 3的节点中交换 6指针。因此， 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)，它会在数据为 next和 3的节点中交换 6指针。因此， 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>;而是包含您需要的标题。对于此示例，您只需要#include <cstdio>即可。

使node成为private的linkedList实现细节。稳健性倾向于随着封装而增加。如果没有人知道linkedList使用的数据结构，则限制其他代码可以执行的操作。由于考虑的可能性更少，因此更容易确保您考虑了所有这些。

不要声明从未使用过的字段(linkedList::tail)。有人会想在某个时候使用该字段，而不会意识到它包含垃圾。

(还有其他改进。在我看来，这三个是最重要的。)