Three ways to solve this problem in Python (build-in sort, merge and priority queue)


  • 7
    C

    I figured out that OJ converts Python list into a ListNode automatically, so in my solution I return a list directly(Sorry for my laziness)

    The first solution uses Python build-in sort, to my surprise it's the fastest one, although it's kind of a hack:

    def mergeKLists(lists):
        ret = []
        for lst in lists:
            while lst:
                ret.append(lst.val)
                lst = lst.next
                
        return sorted(ret)
    

    The second solution uses merge sort:

    def mergeKLists(lists):
        
        def merge(lst1, lst2):
            dummy = pt = ListNode(-1)
            while lst1 and lst2:
                if lst1.val < lst2.val:
                    pt.next = lst1
                    lst1 = lst1.next
                else:
                    pt.next = lst2
                    lst2 = lst2.next
                pt = pt.next
                
            pt.next = lst1 if not lst2 else lst2
            return dummy.next
            
        
        if not lists:
            return None
    
        if len(lists) == 1:
            return lists[0]
        mid = len(lists)/2
        left = mergeKLists(lists[:mid])
        right = mergeKLists(lists[mid:])
    
        return merge(left, right)
    

    The third one uses priority queue:

    import heapq
    def mergeKLists(lists):
            
        ret, heap = [], []
        for lst in lists:
            while lst:
                heapq.heappush(heap, lst.val)
                lst = lst.next
    
        while heap:
            ret.append(heapq.heappop(heap))
        return ret

  • 0
    R

    Hi, I have a question about second solution. When you divided lists, the left part [:mid], the right part[mid :]. Why the right part couldn’t start at (mid+1)? I think it is similar to the binary search: left [:mid], right[mid + 1:]. Thanks.


  • 0
    C

    hi there, please think about a list as [ [2,2,2], [1,1,1], [3,3,3] ], if you skipped the middle one, the result would be [2,2,2,3,3,3], which is incorrect obviously, in fact, I think this method should be called divide and conquer rather than binary search :)


  • 0
    W

    [:mid] means from 0 to mid - 1, that might be the reason why author didn't use [mid +1:] as the second part while divide


  • 1

    "I figured out that OJ converts Python list into a ListNode automatically"

    I think what really happens is that the OJ serializes the result to a string, and both Python lists and ListNode lists look the same when serialized (if they have the same contents).

    In any case, I think it's bad to exploit this. It's wrong, and it makes your solutions incomparable to those that do it right.


  • 0
    P

    thanks for sharing. what's the complexity of heapq version?


  • 2
    P

    Thanks for sharing. Based on your sort() version, I implemented version that returns linked list rather than array.

    class Solution(object):
        def mergeKLists(self, lists):
            res = []
            for l in lists:
                while l:
                    res.append((l.val, l))
                    l = l.next
            
            res.sort(key=lambda tup: tup[0])
            
            dummy = ListNode(None)
            cur = dummy
            
            for l in res:
                cur.next = l[1]
                cur = cur.next
            
            return dummy.next

  • 0
    W

    I think it should be O(N logN).


  • 0
    S

    I think the third solution's time complexity is quite high.


  • 0
    D

    @chris.zhang.336 How do we analyze the time complexity of these solutions? In my opinion, the priority queue solution takes O(nlgk), the merge sort solution has the same level of asymptotic time complexity, because n/k * lgk * k = nlgk (each list, whose length is n/k, will be scanned lgk times).


  • 0

    This heap solution is NlogN and we can do better with a NKlogK solution since K is most likely minimal relative to N.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.