Python 133ms solution


  • 9
    D
    from operator import attrgetter
    
    class Solution:
        # @param a list of ListNode
        # @return a ListNode
        def mergeKLists(self, lists):
            sorted_list = []
            for head in lists:
                curr = head
                while curr is not None:
                    sorted_list.append(curr)
                    curr = curr.next
    
            sorted_list = sorted(sorted_list, key=attrgetter('val'))
            for i, node in enumerate(sorted_list):
                try:
                    node.next = sorted_list[i + 1]
                except:
                    node.next = None
    
            if sorted_list:
                return sorted_list[0]
            else:
                return None

  • 0
    H

    To surprise this is much faster than my standard solution.
    The time complexity is o(n) in your case. Timesort rocks!


  • 1
    H

    Why o(n)? there is a sort operation


  • 1
    R

    This problem should be O(nlogn), but the internal timsort is so fast. Timsort is really good for partial sort sequences. In this case, it is almost O(n)!


  • 0
    T

    Is this good? All the nodes are put into sorted_list. I wonder this may cause any memory problem or not.


  • 0
    S

    @Tony_Zhao I thought it just make reference to "ListNode" object when creating list, so only several pointers are created


  • 0
    H

    @duke8253
    This made more sense to me for the second half, and is a little cleaner:

    for i in range(len(sorted_list) - 1):
        sorted_list[i].next = sorted_list[i + 1]
    
    return sorted_list[0] if sorted_list else None
    

    Similar nonetheless!


  • 0
    A
    This post is deleted!

  • 0
    A
    This post is deleted!

  • 0
    A

    I've an optimization for anyone interested change the sortied line with

    sorted_list = sorted(sorted_list, key=lambda x: x.val)
    

    The run-time by using lambda is 99ms


Log in to reply
 

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