在链表中合并排序

Question

在这段代码中，我试图在链表中实现mergeSort。我的样本输入1 23 5 6 8 5 48 5 8 65-1。但在程序完成后，它既不显示任何输出，也不显示排序后的链表的地址，也不表示整个链表。我想我的列表在mergeSort函数中丢失了。但我不知道在哪里。很抱歉我的提问方式，我是这里的新手。

class Node{
public:
int data;
Node *next;
Node(int data){
this->data = data ;
this->next = NULL ;
}
};
Node* takeInput(){
int data ;
cin >> data;
Node *head = NULL ;
Node *tail = NULL ;
while ( data != -1 ) {
Node* newNode = new Node(data);
if(head == NULL) head = newNode , tail = newNode ;
else {
tail->next = newNode;
tail = newNode;
}
cin >> data ;
}
return head ;
}    
//print data of Linked List.
void print(Node *head ){
Node *temp = head ;
while( temp!= NULL ){
cout << temp->data << "  " ;
temp = temp->next ;
}
}
Node* MidNode(Node* head){
Node *fast = head->next ;
Node *slow  = head ;
while(fast->next != NULL || fast != NULL){
slow = slow->next;
fast = fast->next;
fast = fast->next;
}
return slow;
}
Node* mergeLL(Node *h1 , Node *h2){
Node *head = NULL , *tail = NULL;
if(h1->data < h2->data) {
head = h1 ;
tail = h1;
h1 = h1->next;
}
else {
head = h2 ;
tail = h2 ;
h2 = h2->next;
}
while (h1 != NULL and h2 != NULL){
if(h1->data > h2->data){
tail->next = h2;
tail = tail->next;
h2 = h2->next;
}
else {
tail->next = h1 ;
tail = tail->next ;
h1 = h1->next;
}

}
while( h2 != NULL){
tail->next = h2 ;
tail = tail->next;
h2 = h2->next;
}
while( h1 != NULL ){
tail->next = h1 ;
tail = tail->next;
h1 = h1->next;
}
return head ;
}

Node* mergeSort(Node *head ){
if(head == NULL || head->next == NULL) return head  ;
Node *mid = MidNode(head);
Node *leftList = head;
Node *rightList = mid->next ;
mid->next = NULL ;
leftList = mergeSort(leftList);
rightList = mergeSort(rightList);
return mergeLL(leftList , rightList);

}

int main(){
Node* head2 = takeInput();

Node* ans = mergeSort(head2 );    
cout << ans <<endl;
print(ans);
return 0 ;
}

Answer 1

在MidNode函数中，您有：

while(fast->next != NULL || fast != NULL){
//...
}

如果fast为NULL怎么办？您可以取消引用NULL指针并进入UB领域。

你的意思可能是：while(fast != NULL && fast->next != NULL)。请注意，代码中的偶数操作都不正确。

接下来，在这个循环中：

slow = slow->next;
fast = fast->next;
fast = fast->next;

出于同样的原因，您有机会再次获得UB。您需要添加支票：

slow = slow->next;
fast = fast->next;
if (fast != NULL)
fast = fast->next;

我还没有检查其余的代码，所以可能还有更多的问题。