链表的归并排序

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

typedef struct LNode* LinkList;
struct LNode {
    int data;
    LinkList next;
    LNode(int x = 0) { data = x, next = NULL; }
};

LinkList creatList(int n) {
    LinkList head = new LNode(n);
    LinkList p, tail = head;
    for (int i = 0; i < n; i++) {
        p = new LNode();
        cin >> p->data;
        tail->next = p;
        tail = p;
    }
    return head;
}

void unionList(LinkList head, LinkList head1, LinkList head2) {
    LinkList p = head1->next, q = head2->next, tail = head;
    int cnt1 = 0, cnt2 = 0;
    while (cnt1 < head1->data && cnt2 < head2->data) {
        if (p->data > q->data) {
            tail->next = q;
            tail = q;
            q = q->next;
            cnt2++;
        } else {
            tail->next = p;
            tail = p;
            p = p->next;
            cnt1++;
        }
    }
    if (cnt1 < head1->data) tail->next = p;
    if (cnt2 < head2->data) tail->next = q;
}

void sortList(LinkList head) {
    if (head->data <= 1) return;
    LinkList head1 = new LNode(head->data >> 1);
    LinkList head2 = new LNode(head->data - head1->data);
    head1->next = head->next;
    head2->next = head->next;
    for (int i = 0; i < head1->data; i++) head2->next = head2->next->next;
    sortList(head1);
    sortList(head2);
    unionList(head, head1, head2);
    delete (head1);
    delete (head2);
}

void printList(LinkList head) {
    LinkList p = head->next;
    int cnt = 1;
    while (cnt <= head->data) {
        cout << p->data;
        if (cnt < head->data)
            cout << ‘ ‘;
        else
            cout << ‘\n‘;
        p = p->next;
        cnt++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(), cout.tie();
    int n;
    cin >> n;
    LinkList head = creatList(n);
    sortList(head);
    printList(head);
    return 0;
}

链表的归并排序

原文：https://www.cnblogs.com/sdutzxr/p/13760653.html