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 递归，你忽略了它的返回值。这个返回值很重要。