leetcode [23] 合并K个排序链表

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

这里借助了合并两个链表的代码，可以两两合并，直到只剩一个。注意的细节：由于可能存在奇数个链表，因此在两两合并的时候添加一个空链表，保证不会越界。

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(0)
        head_ = head
        while l1 and l2:
            if l1.val < l2.val:
                head.next = l1
                l1 = l1.next
            else:
                head.next = l2
                l2 = l2.next
            head = head.next
        if l1 or l2:
            l = l1 if l1 else l2
            while l:
                head.next = l
                l = l.next
                head = head.next
        return head_.next
    
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if len(lists) == 0: return None
        if len(lists) == 1: return lists[0]
        result = []
        leng = len(lists)
        lists.append(None)
        for i in range(0, leng, 2):
            result.append(self.mergeTwoLists(lists[i], lists[i + 1]))
        if len(result) == 1:
            return result[0]
        else:
            return self.mergeKLists(result)