Merge k Sorted Lists - LeetCode
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 won't exceed 10^4.
- code
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def mergeTwo(l1, l2):
if not l1: return l2
if not l2: return l1
if l1.val > l2.val: l1, l2 = l2, l1 # start from l1
res = ListNode(0, l1)
while l2:
if l1.next:
if l1.val <= l2.val < l1.next.val:
l2_to_insert = l2
l2 = l2.next
l2_to_insert.next = l1.next
l1.next = l2_to_insert
l1 = l1.next
else:
l1.next = l2
break
return res.next
if not lists or lists == [[]]: return None
res = lists.pop()
while lists:
l = lists.pop()
res = mergeTwo(res, l)
return res
- code #divideConquer
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def mergeTwo(l1, l2):
res = l = ListNode()
while l1 and l2:
if l1.val < l2.val: l.next, l1 = l1, l1.next
else: l.next, l2 = l2, l2.next
l = l.next
l.next = l1 or l2
return res.next
if not lists or lists == [[]]: return None
interval = 1
while interval < len(lists):
for i in range(0, len(lists) - interval, interval * 2):
lists[i] = mergeTwo(lists[i], lists[i + interval])
interval *= 2
return lists[0]
- code #priorityQueue
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
h = [(l.val, idx) for idx, l in enumerate(lists) if l]
heapq.heapify(h)
head = cur = ListNode()
while h:
val, idx = heapq.heappop(h)
cur.next = lists[idx]
cur = cur.next
lists[idx] = lists[idx].next
if lists[idx]:
heapq.heappush(h, (lists[idx].val, idx))
return head.next