Three different Python solutions [122ms is fastest]


  • 0

    Python solution in 122ms:

    class Solution(object):
        def mergeKLists(self, lists):
            """
            :type lists: List[ListNode]
            :rtype: ListNode
            
            For n linked lists of m nodes:
            
            Time: O(n * m * log(n * m))
            Space: O(n * m)
            
            """
            def walk(node):
                while node:
                    yield node.val
                    node = node.next
                    
            a = []
            for node in lists:
                a.extend(walk(node))
    
            a.sort()
            
            head = node = ListNode(None)
            for v in a:
                node.next = ListNode(v)
                node = node.next
                
            return head.next
    

    The above is more "Pythonic" and uses as much of the standard library functionality as possible. This is why it has reasonable speed at the cost of some extra memory consumption.

    Your interviewer will likely be more interested in the following solution:

    class Solution(object):
        def mergeKLists(self, lists):
            """
            :type lists: List[ListNode]
            :rtype: ListNode
            
            For n linked lists of m nodes:
            
            Time: O(n**2 * m)
            Space: O(n * m)
            
            """    
            head = tail = None
            
            lists = [node for node in lists if node is not None]
            values = [node.val for node in lists if node is not None]
            
            while lists:
                min_val = min(values)
                
                if head is None:
                    head = tail = ListNode(min_val)
                else:
                    tail.next = ListNode(min_val)
                    tail = tail.next
                
                idx = values.index(min_val)
                next = lists[idx].next
                if next is None:
                    del lists[idx]
                    del values[idx]
                else:
                    lists[idx] = next
                    values[idx] = next.val
                    
            return head
    

    This is slow [1400ms], since fine grained logic is expressed in Python.

    Another solution would be to copy all values into a heap, then construct the resulting linked list from that:

    # See: https://docs.python.org/2/library/heapq.html
    from heapq import heappush, heappop
    
    class Solution(object):
        def mergeKLists(self, lists):
            """
            :type lists: List[ListNode]
            :rtype: ListNode
            
            For n linked lists of m nodes:
            
            Time: O(n * m * log(n * m))
            Space: O(n * m)
            
            """
            # Max-heap
            heap = []
            
            # Copy all values into the heap
            for node in lists:
                while node is not None:
                    heappush(heap, node.val)
                    node = node.next
            
            # Construct linked list from heap values
            head = node = ListNode(None)
            while heap:
                node.next = ListNode(heappop(heap))
                node = node.next
                
            return head.next
    

    It runs in 166ms


  • 0

    You mean m nodes in each list or m nodes overall? Your stated complexities don't make much sense.


  • 0

    @StefanPochmann Good point, I've just noticed before reading your message and fixed it.

    n is the number of linked lists, m is the "average" number of items per each list, so n * m is the approximate number of total items. Maybe I should have introduced m as the total number of linked list items here...


Log in to reply
 

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