[数据结构与算法]基于链表的两个非递减有序序列的合并

将两个非递减有序序列合并为另一个非递增有序序列。

输入样例：
5 5
1 3 5 7 9
2 4 6 8 10
5 6
1 2 2 3 5
2 4 6 8 10 12
0 0

输出样例：
10 9 8 7 6 5 4 3 2 1
12 10 8 6 5 4 3 2 2 2 1

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

LinkList ListInit();
void ListDestroy(LinkList *head);
void ListTailInsert(LinkList head, int x);
void ListShow(LinkList head);
void ListMerge(LinkList A, LinkList B);
void ListInvert(LinkList head);

int main() {
    int m, n;

    while (scanf("%d %d%*c", &m, &n) && m && n) {
        LinkList A = ListInit();
        LinkList B = ListInit();
        int x;

        for (int i = 0; i < m; i++) {
            scanf("%d%*c", &x);
            ListTailInsert(A, x);
        }
        for (int i = 0; i < n; i++) {
            scanf("%d%*c", &x);
            ListTailInsert(B, x);
        }
        ListMerge(A, B);
        ListShow(A);
        ListDestroy(&A);
        ListDestroy(&B);
    }
    return 0;
}

LinkList ListInit() {
    LinkList head = (LinkList) malloc(sizeof(LNode));

    head->data = 0;
    head->next = NULL;
    return head;
}

void ListDestroy(LinkList *head) {
    LNode *tmp;

    while (*head) {
        tmp = *head;
        *head = (*head)->next;
        free(tmp);
    }
}

void ListTailInsert(LinkList head, int x) {
    LNode *newNode = (LNode *) malloc(sizeof(LNode)), *tail = head;

    newNode->data = x;
    newNode->next = NULL;
    while (tail->next) tail = tail->next;
    tail->next = newNode;
}

void ListShow(LinkList head) {
    for (LNode *cursor = head->next; cursor; cursor = cursor->next) {
        printf("%d%c", cursor->data, cursor->next ? 32 : 10);
    }
}

void ListMerge(LinkList A, LinkList B) {
    LNode *curA = A, *curB = B, *tmp;

    while (curA->next && curB->next) {
        if (curA->next->data < curB->next->data) {
            curA = curA->next;
        } else {
            /*将curB->next结点插入到curA->next位置*/
            tmp = curB->next->next;
            curB->next->next = curA->next;
            curA->next = curB->next;
            curB->next = tmp;
            curA = curA->next;
        }
    }
    if (curB->next) {
        curA->next = curB->next;
        curB->next = NULL;
    }
    ListInvert(A);
}

void ListInvert(LinkList head) {
    LNode *cursor = head->next, *tmp;

    head->next = NULL;
    while (cursor) {
        tmp = cursor->next;
        cursor->next = head->next;
        head->next = cursor;
        cursor = tmp;
    }
}