# my straightforward python solution exceeded time limit, anyone help?

• ``````# 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):
"""
- 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

``````

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