合并对链表的排序

Question

我正在尝试对链表进行合并排序。

我保持全局变量不变，并应用了基本算法，即分而治之。

我不明白为什么会出现细分错误。

我知道我可以通过引用来做，但是我仍然需要知道为什么会这样。

#include <bits/stdc++.h>

using namespace std;

class Node {
  public:
    int data;
    Node *next;
};
Node *head;

void push(Node **head_ref, int x) {
    Node *temp = new Node();
    temp->next = *head_ref;
    temp->data = x;
    *head_ref = temp;
}

void split(Node *temp, Node **a, Node **b) {
    Node *slow;
    Node *fast;
    slow = temp;
    fast = temp->next;
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    *a = temp;
    *b = slow->next;
    slow->next = NULL;
}

Node *mergesort(Node *a, Node *b) {
    if (a == NULL) {
        return b;
    } else
    if (b == NULL) {
        return a;
    }
    if (a->data < b->data) {
        a->next = mergesort(a->next, b);
        return a;
    } else {
        b->next = mergesort(a, b->next);
        return b;
    }
}  

void merge(Node **head_ref) {
     Node *head = *(head_ref);
     Node *a;
     Node *b;
     if (head == NULL || head->next == NULL) {
         return;
     }
     split(head, &a, &b);
     merge(&a);
     merge(&b);
     head = mergesort(a, b);
}

void print(Node *n) {
    while (n != NULL) {
        cout << n->data << " ";
        n = n->next;
    }
}

我的主要方法如下：

int main() {
    Node *head;
    push(&head, 1);
    push(&head, 3);
    push(&head, 6);
    push(&head, 4);
    push(&head, 2);
    print(head);
    merge(&head);
    cout << endl;
    print(head);
}

Answer 1

您的代码中有一些简单的错误：

• head被定义为全局变量，但在main中也被定义为局部变量，因此此局部变量在main内部而不是全局变量中使用。确实不需要全局变量。

• Node *head;中的局部变量main()未初始化。所有push调用都将成功，从而构造一个head指向的列表，但在next之后具有1节点的未定义指针，print将在尝试取消引用该指针时崩溃。该行为是未定义的，您可能偶然在head中使用了空指针，但您可能改而使用了无效的指针，从而导致未定义的行为。初始化head至NULL：

      Node *head = NULL;
  

• 在merge的末尾，您不会通过head_ref更新头指针，因此不会更新调用方中的变量。写这个：

      *head_ref = mergesort(a, b);
  

注意，merge接收Node *head指针并返回更新的Node *头指针会更简单。

还请注意，您的函数名称令人困惑：merge应命名为mergesort，反之亦然。

这里是修改后的版本：

#include <bits/stdc++.h>

using namespace std;

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

void push(Node **head_ref, int x) {
    Node *temp = new Node();
    if (temp) {
        temp->next = *head_ref;
        temp->data = x;
        *head_ref = temp;
    }
}

void split(Node *temp, Node **a, Node **b) {
    Node *slow = temp;
    Node *fast = temp->next;
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    *a = temp;
    *b = slow->next;
    slow->next = NULL;
}

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

Node *mergesort(Node *head) {
     Node *a;
     Node *b;
     if (head == NULL || head->next == NULL) {
         return head;
     }
     split(head, &a, &b);
     a = mergesort(a);
     b = mergesort(b);
     return merge(a, b);
}

void print(const Node *n) {
    while (n != NULL) {
        cout << n->data << " ";
        n = n->next;
    }
    count << endl;
}

int main() {
    Node *head = NULL;
    push(&head, 1);
    push(&head, 3);
    push(&head, 6);
    push(&head, 4);
    push(&head, 2);
    print(head);
    head = mergesort(head);
    print(head);
    return 0;
}