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

链表排序代码如下：

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

def sortList(head):
    if not head or not head.next:
        return head
    mid = getMid(head)
    left = sortList(head)
    right = sortList(mid)
    return merge(left, right)

def getMid(head):
    if not head:
        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
    return mid

def merge(left, right):
    dummy = Node(0)
    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 or right
    return dummy.next

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

def mergeTwoLists(l1, l2):
    dummy = Node(0)
    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 or l2
    return dummy.next

使用示例：

# 排序链表
head = Node(3)
head.next = Node(2)
head.next.next = Node(1)
head = sortList(head)
while head:
    print(head.val, end=' ')
    head = head.next

# 合并两个有序链表
l1 = Node(1)
l1.next = Node(2)
l1.next.next = Node(4)

l2 = Node(1)
l2.next = Node(3)
l2.next.next = Node(4)

head = mergeTwoLists(l1, l2)
while head:
    print(head.val, end=' ')
    head = head.next

输出结果为：

1 2 3 
1 1 2 3 4 4