Problem
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
-10^4 <= lists[i][j] <= 10^4
lists[i]
is sorted in ascending order.- The sum of
lists[i].length
will not exceed10^4
.
Test Cases
[[1,4,5],[1,3,4],[2,6]]
[]
[[]]
[[1,2,2],[1,1,2]]
Solution
Solution 1: Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
import heapq
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
ans = node = ListNode()
hp = list()
continue_run = True
remove_none = False
count = 0
while continue_run:
if len(lists):
for i, l in enumerate(lists):
if l:
heapq.heappush(hp, (l.val, count, l))
lists[i] = l.next
count += 1
else:
remove_none = True
if remove_none:
lists = [x for x in lists if x is not None]
remove_none = False
if len(hp):
(_, _, node.next) = heapq.heappop(hp)
node = node.next
else:
continue_run = False
return ans.next
Solution 2: Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
import heapq
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
ans = node = ListNode()
hp = list()
count = 0
for l in lists:
if l:
heapq.heappush(hp, (l.val, count, l))
count += 1
while len(hp):
(_, _, l) = heapq.heappop(hp)
if l.next:
heapq.heappush(hp, (l.next.val, count, l.next))
count += 1
node.next = l
node = l
return ans.next
Here,
I use
count
as a second member for comparison for case when tuples has samel.val
- I could have used list indices as second member but they could also conflict.
- Because
count
will always be unique
Time complexity is
O(nlogk)
- Breakup:
O(klogk + n+ (n-k)logk))
- Breakup: