c++1）实现链表的排序(升序) 2）实现两个有序链表的合并：A=A∪B，要求合并后仍然有序。 提交前请将所有的提示信息去掉，只保留最后的输出结果。例如运行时：从键盘直接输入： 2 1 2 3 1 2 3 输出结果为： 1 2 3 分别表示第一个链表元素个数为2，元素分别为 1,2 ；第二个链表元素个数为3，元素分别为1,2,3。

1）链表排序的实现：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head; // 链表为空或只有一个节点，直接返回
    ListNode* slow = head;
    ListNode* fast = head->next;
    while (fast && fast->next) { // 快慢指针寻找中间节点
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* mid = slow->next; // 中间节点
    slow->next = NULL; // 断开链表
    ListNode* left = sortList(head); // 递归排序左半部分
    ListNode* right = sortList(mid); // 递归排序右半部分
    ListNode* dummy = new ListNode(0); // 定义虚拟头结点
    ListNode* cur = dummy;
    while (left && right) { // 合并左右两个排序好的链表
        if (left->val < right->val) {
            cur->next = left;
            left = left->next;
        } else {
            cur->next = right;
            right = right->next;
        }
        cur = cur->next;
    }
    cur->next = left ? left : right; // 将剩余的节点连接到链表末尾
    return dummy->next; // 返回新的头结点
}

int main() {
    ListNode* head = new ListNode(2);
    head->next = new ListNode(1);
    head->next->next = new ListNode(3);
    ListNode* sorted = sortList(head);
    while (sorted) {
        cout << sorted->val << " ";
        sorted = sorted->next;
    }
    cout << endl;
    return 0;
}

2）有序链表的合并实现：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0); // 定义虚拟头结点
    ListNode* cur = dummy;
    while (l1 && l2) { // 合并两个有序链表
        if (l1->val < l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    cur->next = l1 ? l1 : l2; // 将剩余的节点连接到链表末尾
    return dummy->next; // 返回新的头结点
}

int main() {
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(2);
    l1->next->next = new ListNode(3);
    ListNode* l2 = new ListNode(1);
    l2->next = new ListNode(2);
    l2->next->next = new ListNode(3);
    ListNode* merged = mergeTwoLists(l1, l2);
    while (merged) {
        cout << merged->val << " ";
        merged = merged->next;
    }
    cout << endl;
    return 0;
}