C ++链表的合并排序没有对前两个索引进行排序

Question

我在试图弄清楚如何递归合并排序链接列表时有些困惑。我尝试遵循一些指南，但是所有指针和递归都让我有些迷茫。一旦列表中的每个节点只有一个节点，就好像合并函数存在问题。

我有一个Node类和一个列表类。我省略了其他成员函数以使其更具可读性。这是课程。抱歉，某些变量名在函数中不是最好的。

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

    class Linked_list {
   private:
       unsigned int length;
       Node *head;
       Node *tail;
    public:
       void sort_ascending();
       void merge_sort(Node **);
       void halve(Node *&, Node *&, Node *&);
       Node* merge(Node *, Node *);
 };

我从sort_ascending（）开始，它将创建一个Node指针并将其设置为列表中的第一个节点，然后使用该指针作为参数调用merge_sort。

void Linked_list::sort_ascending(){
   Node *h = head->next;
   merge_sort(&h);
}

merge_sort检查前两个索引是否为NULL，如果为空则返回。否则，链接列表将减半。

void Linked_list::merge_sort(Node **h) {
    Node *t = *h;
    Node *a;
    Node *b;
    if((t == NULL) || (t->next == NULL)){
         return;
    }
    halve(t, a, b);
    merge_sort(&a);
    merge_sort(&b);
    *h = merge(a, b);
         return;
}

这里是将列表分成两半的功能。

void Linked_list::halve(Node *&t, Node *&a, Node *&b){
         Node *h1 = t;
         Node *h2 = t->next;
         while(h2 != NULL){
                 h2 = h2->next;
                 if(h2 != NULL){
                         h1 = h1->next;
                         h2 = h2->next;
                 }
         }
         a = t;
         b = h1->next;
         h1 -> next = NULL;
}

最后是合并功能。

Node* Linked_list::merge(Node *a, Node *b){
         Node *h = NULL;
         if(a == NULL){
                 return b;
         }
         if(b == NULL){
                 return a;
         }
         if(a->val <= b->val){
                 h = a;
                 h->next = merge(a->next, b);
         }else{
                 h = b;
                 h->next = merge(a, b->next);
         }
         return h;
}

当我运行程序并输入/打印一些值时，我得到：

9 4 32 2 6

然后当我对它进行排序时，输出变为：

9 4 2 6 32

Answer 1

在sortAscending函数中

void Linked_list::sort_ascending(){
   Node *h = head->next;
   merge_sort(&h);
}

参见上面，您将node * h指向头的下一个。自己不要头。也许那就是为什么它排除了第一项，即在对链表进行排序时标头本身。