- Merge K Sorted Lists
Merge k sorted linked lists and return it as one sorted list.
LC: 23
Analyze and describe its complexity.
Example
Given lists:
[
2->4->null,
null,
-1->null
],
return -1->2->4->null.
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
import heapq
class Type:
def __init__(self, li):
self.li = li
def __lt__(self, other):
return self.li.val - other.li.val < 0
def __gt__(self, other):
return self.li.val - other.li.val > 0
def __eq__(self, other):
return self.li.val - other.li.val == 0
class Solution:
"""
@param lists: a list of ListNode
@return: The head of one sorted list.
"""
def mergeKLists(self, lists):
heap = []
for li in lists:
if not li:
continue
heapq.heappush(heap, Type(li))
dummy = trav = ListNode(-1)
while heap:
li_type = heapq.heappop(heap)
trav.next = li_type.li
trav = trav.next
li_type.li = li_type.li.next
if li_type.li:
heapq.heappush(heap, li_type)
return dummy.next
- Time:
O(nklog(k)) - Space:
O(k)for constructing priority queue
Notes:
- I practiced constructing comparator here. It should be noted that heap queue is min heap. So it is fine if I am to sort ascending numbers.
- Another key point of this problem is to traverse linked list.
- It is important to use
dummy = ListNode(-1)and thenreturn dummy.nextat the end. - Also, it should be coupled with
trav = dummyand traverse all linked lists.
- It is important to use
- As mentioned in here, the operator module functions allow multiple levels of sorting. I could put
(list.val, list)into heap queue so thatheapis sorted by head node's value (ascending order).
