问题描述： 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, val=0, next=None):
        self.val = val
        self.next = next

def merge_sort(head):
    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 = merge_sort(head), merge_sort(mid)
    dummy = ListNode()
    cur = dummy
    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 dummy.next

def merge_two_lists(l1, l2):
    dummy = ListNode()
    cur = dummy
    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 dummy.next

n1 = int(input())
vals1 = list(map(int, input().split()))
n2 = int(input())
vals2 = list(map(int, input().split()))

head1 = tail1 = ListNode()
for val in vals1:
    tail1.next = ListNode(val)
    tail1 = tail1.next
head1 = head1.next

head2 = tail2 = ListNode()
for val in vals2:
    tail2.next = ListNode(val)
    tail2 = tail2.next
head2 = head2.next

sorted_head1 = merge_sort(head1)
sorted_head2 = merge_sort(head2)

merged_head = merge_two_lists(sorted_head1, sorted_head2)

while merged_head:
    print(merged_head.val, end=' ')
    merged_head = merged_head.next

输入示例：

2
1 2
3
1 2 3

输出示例：

1 1 2 2 3