交换链表的最后一个节点将进入无穷大 -- C++

下面是代码，

#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("NULLn");
}
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->无 1->2->6->3->无

对于链表 #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-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-> 没有尽头

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

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

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

实现中缺少这部分代码。

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

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指针。因此，头部指针将指向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节点的指针将变为 null。

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节点的指针将变为 null。这是第一种情况中发生的事情，那么它会成功吗？

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成为linkedList的private实现细节。鲁棒性往往随着封装而增加。如果没有人知道linkedList使用的数据结构，则限制其他代码可以执行的操作。由于要解释的可能性较少，因此更容易确保您考虑了所有这些可能性。
不要声明从未使用的字段 (linkedList::tail)。有人会想在某个时候使用该字段，而没有意识到它包含垃圾。

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

相关内容

最新更新

热门标签：