合併排序鏈接列表

Question

我需要使用合併排序對鏈接列表進行排序。我把這些代碼放在一起，但我遇到了一個奇怪的錯誤。

我的鏈接列表由隨機數填充。但是，在排序後，它只會按排序順序顯示比鏈表第一個元素大的數字。

下面是我的一些代碼：

node* MergeSort(node *my_node) 
{ 
    node *secondNode; 

    if (my_node == NULL) 
     return NULL; 
    else if (my_node->next == NULL) 
     return my_node; 
    else 
    { 
     secondNode = Split(my_node); 
     return Merge(MergeSort(my_node),MergeSort(secondNode)); 
    } 
} 

node* Merge(node* firstNode, node* secondNode) 
{ 
    if (firstNode == NULL) return secondNode; 
    else if (secondNode == NULL) return firstNode; 
    else if (firstNode->number <= secondNode->number) //if I reverse the sign to >=, the behavior reverses 
    { 
     firstNode->next = Merge(firstNode->next, secondNode); 
     return firstNode; 
    } 
    else 
    { 
     secondNode->next = Merge(firstNode, secondNode->next); 
     return secondNode; 
    } 
} 

node* Split(node* my_node) 
{ 
    node* secondNode; 

    if (my_node == NULL) return NULL; 
    else if (my_node->next == NULL) return NULL; 
    else { 
     secondNode = my_node->next; 
     my_node->next = secondNode->next; 
     secondNode->next = Split(secondNode->next); 
     return secondNode; 
    } 
} 

Answer 1

我曾嘗試你的代碼和它完美的作品。

你在最後看過正確的列表嗎？ 您的新列表頭不是前一個頭，而是合併函數的返回值 。

printList(myList); 
node* sortedList = MergeSort(myList); 
printList(sortedList); //whole list sorted 
printList(myList); //list (of elements not smaller that first element) sorted 

和的printList（）是明顯的作用：

void printList(node* my_node){ 
    if(my_node == NULL) return; 
    else { 
     std::cout<<my_node->number<<" "<<std::endl; 
     printList(my_node->next); 
    } 
}