用C++代码：实现链表的排序(升序) ，实现两个有序链表的合并：A=A∪B，要求合并后仍然有序。

链表排序的C++代码：

#include <iostream>
using namespace std;

//链表结点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

//链表插入
void insert(ListNode*& head, int val) {
    ListNode* p = new ListNode(val);
    if (!head) {
        head = p;
        return;
    }
    ListNode* cur = head;
    while (cur->next) {
        cur = cur->next;
    }
    cur->next = p;
}

//链表排序
void sortList(ListNode*& head) {
    if (!head || !head->next) {
        return;
    }
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* mid = slow;
    slow = head;
    fast = mid->next;
    mid->next = NULL;
    sortList(slow);
    sortList(fast);
    ListNode dummy(0);
    ListNode* cur = &dummy;
    while (slow && fast) {
        if (slow->val < fast->val) {
            cur->next = slow;
            slow = slow->next;
        } else {
            cur->next = fast;
            fast = fast->next;
        }
        cur = cur->next;
    }
    cur->next = slow ? slow : fast;
    head = dummy.next;
}

//合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) {
        return l2;
    }
    if (!l2) {
        return l1;
    }
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

//输出链表
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    ListNode* head1 = NULL;
    insert(head1, 3);
    insert(head1, 1);
    insert(head1, 5);
    insert(head1, 2);
    insert(head1, 4);
    cout << "Before sorting: ";
    printList(head1);
    sortList(head1);
    cout << "After sorting: ";
    printList(head1);

    ListNode* head2 = NULL;
    insert(head2, 2);
    insert(head2, 4);
    insert(head2, 6);
    insert(head2, 8);
    cout << "List1: ";
    printList(head1);
    cout << "List2: ";
    printList(head2);
    ListNode* merged = mergeTwoLists(head1, head2);
    cout << "After merging: ";
    printList(merged);

    return 0;
}

输出结果：

Before sorting: 3 1 5 2 4 
After sorting: 1 2 3 4 5 
List1: 1 2 3 4 5 
List2: 2 4 6 8 
After merging: 1 2 2 3 4 4 5 6 8