HackMD
23.Merge k Sorted Lists
tags: Hard,Linked List,Heap,Divide and Conquer
題目描述
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<= 104 - 0 <=
lists[i].length<= 500 - -104 <=
lists[i][j]<= 104 lists[i]is sorted in ascending order.- The sum of
lists[i].lengthwill not exceed 104.
解答
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]
Yen-Chi ChenSun, Mar 12, 2023
