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:

 12345678910 nput: 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:

 12 Input: lists = [] Output: [] 

Constraints:

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.

Related Topics: Linked List Divide and Conquer Heap (Priority Queue) Merge Sort

## 解題邏輯與實作

 123456789101112131415161718192021222324252627282930313233 class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: return self.merged(lists, 0, len(lists)) def merged(self, lists: List[Optional[ListNode]], start_idx: int, end_idx: int) -> Optional[ListNode]: len_list = end_idx-start_idx; if len_list <= 0: return None merged_result = lists[start_idx] if len_list > 1: k = round(len_list/ 2); merged_result = self.mergeTwoLists(self.merged(lists, start_idx, start_idx+k), self.merged(lists, start_idx+k, end_idx)) return merged_result def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: answer = ListNode(-1) head = answer while list1 and list2: if list1.val < list2.val: answer.next = list1 list1 = list1.next else: answer.next = list2 list2 = list2.next answer = answer.next answer.next = list1 if list1 else list2 return head.next 

Runtime 為 112 ms，Beats 是 78.87%。不過它效率比我想像中的還差。

 12345678910111213141516171819202122232425262728293031323334353637383940414243 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: len_list = len(lists) if len_list == 0: return None resules = lists while len_list > 1: if len_list % 2 != 0: resules.append(None) len_list += 1 new_resule = [] for i in range(0, len_list, 2): new_resule.append(self.mergeTwoLists(resules[i], resules[i+1])) resules = new_resule len_list = len(resules) return resules[0] def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: answer = ListNode(-1) head = answer while list1 and list2: if list1.val < list2.val: answer.next = list1 list1 = list1.next else: answer.next = list2 list2 = list2.next answer = answer.next answer.next = list1 if list1 else list2 return head.next 

 12345678910111213141516 class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: head = temp = ListNode() arr = [] for l in lists: while l != None: arr.append(l.val) l = l.next arr.sort() for a in arr: temp.next = ListNode() temp = temp.next temp.val = a return head.next 

## 更新紀錄

• 2023-02-15 發布
• 2023-01-11 完稿
• 2023-01-11 起稿