题解 | #合并k个已排序的链表#

class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        # 两两合并
        def merge(h1, h2):
            if h1 == None:
                return h2
            elif h2 == None:
                return h1
            else:
                head = ListNode(0)
                cur = head
                while h1 and h2:
                    if h1.val <= h2.val:
                        cur.next = h1
                        h1 = h1.next
                    else:
                        cur.next = h2
                        h2 = h2.next
                    cur = cur.next
                cur.next = h1 if h1 else h2
            return head.next
        # 依次两两合并，得到新列表长度如果大于1，继续两两合并
        while len(lists) > 1:
            new_lists = []
            for h1, h2 in zip(lists[0::2], lists[1::2]):
                h = merge(h1, h2)
                new_lists.append(h)
            # 处理落单链表
            if h2 != lists[-1]:
                new_lists[-1] = merge(new_lists[-1], lists[-1])
            lists = new_lists
        if not lists:
            return None
        else:
            return lists[0]