C ++链表合并排序不断丢失节点

Question

我在对链表进行合并排序时遇到问题。出于某种原因，一些节点不断从列表中断开连接。主要问题似乎来自多个条件跳转，因为 1 4 2 3 等列表已排序，尽管有 6 个条件跳转，而 4 2 3 1 丢失所有节点，但值 4 除外。我的代码基于来自 tutorialspoint.com 的代码。

class Node {
  public:
    int val;
    Node *next;
};

class Linked_list {
  private:
    unsigned int length;
    Node *head;

//desc: sorts in ascending order then merges two linked lists
//param: Node*, the lists being sorted
Node* Linked_List::merge_lists_ascend(Node* ll1, Node* ll2) { //function for merging two sorted list
   Node* newhead = NULL;
   if(ll1 == NULL)
      return ll2;
   if(ll2 == NULL)
      return ll1;
   //recursively merge the lists
   if(ll1 -> val <= ll2 -> val) {
      newhead = ll1;
      newhead -> next = merge_lists_ascend(ll1->next,ll2);
   }
   else {
      newhead = ll2;
      newhead -> next = merge_lists_ascend(ll1,ll2->next);
   }
   return newhead;
}

//desc: splits a linked list into two lists
//param: Node*, the list being split; Node**, the two lists that will be filled
//by the split list
void Linked_List::splitList(Node* start, Node** ll1, Node** ll2) {
   Node* slow = start;
   Node* fast = start -> next;
   while(fast != NULL) {
      fast = fast -> next;
      if(fast != NULL) {
          slow = slow -> next;
          fast = fast -> next;
      }
   }
   *ll1 = start;
   *ll2 = slow -> next;
   //spliting
   slow -> next = NULL;
}

//desc: recursive function that runs through the splitting, sorting and merging
//param: Node**, the starting node
Node* Linked_List::merge_sort_ascend(Node* start) {
        Node* head = start;
        Node* ll1;
        Node* ll2;
        //base case
        if(head == NULL || head->next == NULL) {
                return head;
        }
        splitList(head,&ll1,&ll2); //split the list in two halves
        //sort left and right sublists
        ll1 = merge_sort_ascend(ll1);
        ll2 = merge_sort_ascend(ll2);
        //merge two sorted list
        start = merge_lists_ascend(ll1,ll2);
        return start;
}

Answer 1

当您递归调用 merge_sort_ascend 时，您会忽略它的 return 值。 return 值很重要。

C ++链表合并排序不断丢失节点

C++ Linked list merge sort keeps losing nodes

sorting

singly-linked-list

c++11