23.Merge k Sorted Lists === ###### tags: `Hard`,`Linked List`,`Heap`,`Divide and Conquer` [23. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/) ### 題目描述 You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order. *Merge all the linked-lists into one sorted linked-list and return it.* ### 範例 **Example 1:** ``` Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6 ``` **Example 2:** ``` Input: lists = [] Output: [] ``` **Example 3:** ``` Input: lists = [[]] Output: [] ``` **Constraints**: * `k` == `lists.length` * 0 <= `k` <= 10^4^ * 0 <= `lists[i].length` <= 500 * -10^4^ <= `lists[i][j]` <= 10^4^ * `lists[i]` is sorted in **ascending order**. * The sum of `lists[i].length` will not exceed 10^4^. ### 解答 #### Python ```python= class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: def merge2Lists(l1, l2): head = ListNode() cur = head 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 if l1: cur.next = l1 else: cur.next = l2 return head.next N = len(lists) if N <= 0: return None step = 1 while step < N: for i in range(0, N - step, step*2): lists[i] = merge2Lists(lists[i], lists[i + step]) step *= 2 return lists[0] ``` > [name=Yen-Chi Chen][time=Sun, Mar 12, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)