my straightforward python solution exceeded time limit, anyone help?


  • 0
    F
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
            
    def mergeLists(list1, list2):
        dummy = ListNode(0)
        cur = dummy
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
                
            cur = cur.next
        
        if not list1:
            cur.next = list2
        else:
            cur.next = list1
        
        return dummy.next
    
    class Solution:
        """
        @param lists: a list of ListNode
        @return: The head of one sorted list.
        """
        def mergeKLists(self, lists):
            # write your code here
            """ 
            - if we merge [0,1], [0,2]..., it is O(n-1) for n lists.
            - it seems there is no way to be faster than that.
            for merge two list of nodes m,n, m<n, it will be O(m) since we can
            choose to process the list with less nodes. but we don't know
            beforehand which one is shorter, so it will be O((m+n)/2) on average.
            - to handle edge case gracefully, we will use dummy node.
            """
            if not lists:
                return None
            elif len(lists) < 2:
                return lists[0]
                
            list1 = lists[0]
            for list2 in lists[1:]:
                list1 = mergeLists(list1, list2)
            
            return list1
            
    
    
    

Log in to reply
 

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