C++ 实现归并排序（使用单链表）

#include 
#include 
using namespace std;


struct Linklist {
    int val;
    Linklist* next;
    Linklist() {next = nullptr;}
    Linklist(int v) {val = v; next = nullptr;}
};
Linklist* link(vector arr) {
    int n = arr.size();
    Linklist* head = new Linklist;
    Linklist* temp = head;
    for (int i = 0; i < n; i++) {
        temp->val = arr[i];
        if (i != n - 1) {
            temp->next = new Linklist;
            temp = temp->next;
        }
    }
    return head;
} 
void display(Linklist* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}
Linklist* merge(Linklist* lhead, Linklist* rhead) {
    Linklist* head = new Linklist;
    Linklist* temp = head;
    Linklist* temp1 = lhead;
    Linklist* temp2 = rhead;
    while (temp1 && temp2) {
        if (temp1->val < temp2->val) {
            temp->next = temp1;
            temp1 = temp1->next;
        } else {
            temp->next = temp2;
            temp2 = temp2->next;
        }
        temp = temp->next;
    }
    if (temp1)
        temp->next = temp1;
    if (temp2)
        temp->next = temp2;
    return head->next;
}
Linklist* merge_sort(Linklist* head) {
    // 用快慢指针确定中点
    Linklist *quick, *slow;
    quick = slow = head;
    while (quick->next) {
        quick = quick->next;
        if (quick->next) {
            quick = quick->next;
            slow = slow->next;
        }
    }
    // 链表只有一个节点，直接返回
    if (quick == slow)
        return head;
    // 将链表切分为两段
    Linklist* lhead = head;
    Linklist* rhead = slow->next;
    slow->next = nullptr;
    lhead = merge_sort(lhead);
    rhead = merge_sort(rhead);
    head = merge(lhead, rhead);
    return head;
}

int main() {
    vector arr = {3,8,1,9,2,11,15,22,0,87};
    Linklist* head = link(arr);
    head = merge_sort(head);
    display(head);

    return 0;
}