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

链表排序代码如下：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def sortList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    left, right = sortList(head), sortList(mid)
    res = ListNode(0)
    cur = res
    while left and 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 if left else right
    return res.next

合并两个有序链表代码如下：

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    res = ListNode(0)
    cur = res
    while l1 and 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 if l1 else l2
    return res.next

完整代码如下：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def sortList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    left, right = sortList(head), sortList(mid)
    res = ListNode(0)
    cur = res
    while left and 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 if left else right
    return res.next

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    res = ListNode(0)
    cur = res
    while l1 and 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 if l1 else l2
    return res.next

# 读取链表
n1 = int(input())
head1 = ListNode(0)
cur = head1
for i in range(n1):
    node = ListNode(int(input()))
    cur.next = node
    cur = cur.next

n2 = int(input())
head2 = ListNode(0)
cur = head2
for i in range(n2):
    node = ListNode(int(input()))
    cur.next = node
    cur = cur.next

# 排序链表
sort_head1 = sortList(head1.next)
sort_head2 = sortList(head2.next)

# 合并有序链表
merged_head = mergeTwoLists(sort_head1, sort_head2)

# 输出结果
while merged_head:
    print(merged_head.val, end=' ')
    merged_head = merged_head.next