在双链表上插入排序有什么问题?

Question

我得到一些随机结果。我已经完成了流程，并做了几次试运行，但不能确切地找出代码的问题所在。

程序流程:链表:5 4 3 2 1

1. 当前位于第2位，即4，也将此值存储到变量temp中。
2. previous在第1位，即5
3. 第一个while循环运行直到current变为null。
4. 第二个嵌套while循环与条件tempdata一起从当前节点的前身运行到头节点。如果condition为真，则将temp移到正确的位置。
5. 最后重复第一个循环。

#include <iostream>
using namespace std;
​
class Node {
public:
int data;
Node *next;
Node *prev;
​
Node(int data) {
this->data = data;
next = NULL;
prev = NULL;
}
};
​
void insert(Node *&head, Node *&tail, int data) {
if (head == NULL) {
Node *temp = new Node(data);
temp->next = temp;
head = temp;
tail = temp;
} else {
Node *temp = new Node(data);
tail->next = temp;
temp->prev = tail;
tail = temp;
}
}
​
void display(Node *head) {
Node *temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
​
void insertionSort(Node *&head, int size) {
Node *current = head->next;
Node *previous; 
while (current!= NULL) { 
int temp = current->data;     
previous = current->prev; 
while (previous != head && temp < previous->data) { 
previous->next->data = previous->data; 
previous = previous->prev;             
}
previous->data = temp;   
current = current->next; 
}
}
​
int main() {
Node *head = NULL;
Node *tail = NULL;
int size;
int data;
cout << "Linked-List Size: ";
cin >> size;
cout << "Enter Elements: ";
for (int i = 0; i < size; i++) {
cin >> data;
insert(head, tail, data);
}
display(head);
insertionSort(head, size);
display(head);
}

Answer 1

在绘制发生的情况时手动跟踪代码:

开头是

temp = 4     
previous = current->prev
5 -> 4 -> 3 -> 2 -> 1
^    ^
p    c

现在previous != head为假，因此没有进入循环，并且

previous->data = temp
current = current->next
4 -> 4 -> 3 -> 2 -> 1
^         ^
p         c

这开始看起来很糟糕- 5已经消失了…

下一个迭代:

temp = 3     
previous = current->prev

4 -> 4 -> 3 -> 2 -> 1
^    ^
p    c

previous != head && temp < previous->data为真，因此进入循环:

previous->next->data = previous->data;
4 -> 4 -> 4 -> 2 -> 1
^    ^
p    c
previous = previous->prev;
4 -> 4 -> 4 -> 2 -> 1
^         ^
p         c

现在previous != head为假，退出循环

previous->data = temp
current = current->next
3 -> 4 -> 4 -> 2 -> 1
^              ^
p              c

等等

为了解决这个问题，在编写任何代码之前，画出你的列表和需要发生的事情。
(别忘了处理空列表)