my straightforward python solution exceeded time limit, anyone help?

  • 0
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    # = None
    def mergeLists(list1, list2):
        dummy = ListNode(0)
        cur = dummy
        while list1 and list2:
            if list1.val < list2.val:
       = list1
                list1 =
       = list2
                list2 =
            cur =
        if not list1:
   = list2
   = list1
    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.