问题描述： 1）实现链表的排序(升序) 2）实现两个有序链表的合并：A=A∪B，要求合并后仍然有序。

链表的排序可以采用常见的排序算法，比如冒泡排序、插入排序、选择排序等。这里我们以插入排序为例进行讲解，算法复杂度为O(n^2)。

1. 插入排序

插入排序的基本思想是将一个元素插入到已排序的部分中，使得插入后依然有序。

具体步骤如下：

1. 从链表头开始，定义一个指针p，将p指向链表的第二个节点。
2. 再定义一个指针q，将q指向链表的第一个节点。
3. 对链表进行遍历，将p逐个向后移动。每次将p指向的节点与前面的节点进行比较，如果p指向的节点值小于前面的节点值，则需要将p指向的节点插入到前面的节点之前。
4. 如果p指向的节点值大于或等于前面的节点值，则将p指向下一个节点，继续比较。
5. 遍历完链表后，链表就已经有序了。

代码如下：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
def insertionSortList(head: ListNode) -> ListNode:
    dummy = ListNode(0) # 定义一个哨兵节点
    dummy.next = head
    last_sorted = head # 已排序的最后一个节点
    curr = head.next # 当前需要进行插入排序的节点
    while curr:
        if last_sorted.val <= curr.val:
            last_sorted = last_sorted.next
        else:
            prev = dummy
            while prev.next.val <= curr.val:
                prev = prev.next
            last_sorted.next = curr.next
            curr.next = prev.next
            prev.next = curr
        curr = last_sorted.next
    return dummy.next

2. 两个有序链表的合并

假设两个有序链表分别为A和B，它们的头节点分别为headA和headB。我们需要将两个链表合并成一个新的有序链表C。

具体步骤如下：

1. 定义一个哨兵节点dummy，用来存储新链表C的头节点。
2. 定义指针p和q，分别指向链表A和B的头节点。
3. 遍历链表A和B，比较p和q指向的节点值的大小，将较小的节点插入到新链表C的末尾，并将指针后移。
4. 如果链表A或B中还有节点未处理完，则将剩余的节点直接插入到新链表C的末尾。
5. 返回新链表C的头节点。

代码如下：

def mergeTwoLists(headA: ListNode, headB: ListNode) -> ListNode:
    dummy = ListNode(0)
    curr = dummy
    p, q = headA, headB
    while p and q:
        if p.val <= q.val:
            curr.next = p
            p = p.next
        else:
            curr.next = q
            q = q.next
        curr = curr.next
    if p:
        curr.next = p
    if q:
        curr.next = q
    return dummy.next