合并k个有序链表

要合并k个有序链表，可以使用分治法，将k个链表划分成两半，然后递归地合并左右两半，最后再将左右两半合并成一个有序链表。具体实现如下：

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

def mergeKLists(lists: List[ListNode]) -> ListNode:
    if not lists:
        return None
    n = len(lists)
    if n == 1:
        return lists[0]
    left = mergeKLists(lists[:n//2])
    right = mergeKLists(lists[n//2:])
    return mergeTwoLists(left, right)

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(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 if l1 else l2
    return dummy.next

其中，mergeKLists函数接收一个由k个链表组成的列表，如果列表为空，则返回None；如果列表只有一个元素，则直接返回这个元素，表示已经合并完成；否则，将列表划分成左右两半，分别递归地调用mergeKLists函数，将左右两半合并成一个有序链表，最后返回这个有序链表。

mergeTwoLists函数用于合并两个有序链表，具体操作是，定义一个虚拟头节点dummy和一个游标cur，遍历两个链表，比较当前节点的值，将小的节点接到cur的next上，然后移动cur和对应链表的游标，直到其中一个链表为空，然后将另一个链表的剩余部分接到cur的next上，最后返回dummy.next即为合并后的有序链表。