2018-10-21Merge K Sorted Lists

104. 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:

1. 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.
2. Another key point of this problem is to traverse linked list.
   • It is important to use dummy = ListNode(-1) and then return dummy.next at the end.
   • Also, it should be coupled with trav = dummy and traverse all linked lists.
3. As mentioned in here, the operator module functions allow multiple levels of sorting. I could put (list.val, list) into heap queue so that heap is sorted by head node's value (ascending order).