HackMD
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:
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:
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
解題邏輯與實作
之前有解過寫過一篇 0021. Merge Two Sorted Lists，這題就是它的進階。
我打算按照提示中的分而治之（Divide and Conquer）法與遞迴不斷將鏈結串列剖半對分，直到剩下一個或是兩個鏈結串列時，開始合併與回傳。
以長度為 6 的鏈結串列 [A, B, C, D, E, F] 為例，用遞迴去剖半對分的話最終會是 A、B 排，AB 排後再跟 C 排，再 D、E 排，DE 排後再跟 F 排，最後 ABC 與 DEF 再排一次，總共執行了 5 次。
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%。不過它效率比我想像中的還差。
因此我打算換個寫法試試，一樣是分而治之法，不過把它改成直接兩兩抓來做排序，就是 A、B 排、C、D 排、C、D 排：
# 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)
print("vvvv", len_list)
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
效果出來出乎意料的不錯欸，Runtime 96 ms、Beats 95.64%。
偷看了下 70ms 的答案，因為它直接用 sort 難怪效能不錯 XDDD
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-02-15 發布
- 2023-01-11 完稿
- 2023-01-11 起稿
