# 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 list1 = lists for list2 in lists[1:]: list1 = mergeLists(list1, list2) return list1
my straightforward python solution exceeded time limit, anyone help?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.