Python 133ms solution

• ``````from operator import attrgetter

class Solution:
# @param a list of ListNode
# @return a ListNode
def mergeKLists(self, lists):
sorted_list = []
while curr is not None:
sorted_list.append(curr)
curr = curr.next

sorted_list = sorted(sorted_list, key=attrgetter('val'))
for i, node in enumerate(sorted_list):
try:
node.next = sorted_list[i + 1]
except:
node.next = None

if sorted_list:
return sorted_list[0]
else:
return None``````

• To surprise this is much faster than my standard solution.
The time complexity is o(n) in your case. Timesort rocks!

• Ｗhy o(n)? there is a sort operation

• This problem should be O(nlogn), but the internal timsort is so fast. Timsort is really good for partial sort sequences. In this case, it is almost O(n)!

• Is this good? All the nodes are put into sorted_list. I wonder this may cause any memory problem or not.

• @Tony_Zhao I thought it just make reference to "ListNode" object when creating list, so only several pointers are created

• @duke8253
This made more sense to me for the second half, and is a little cleaner:

``````for i in range(len(sorted_list) - 1):
sorted_list[i].next = sorted_list[i + 1]

return sorted_list[0] if sorted_list else None
``````

Similar nonetheless!

• This post is deleted!

• This post is deleted!

• I've an optimization for anyone interested change the sortied line with

``````sorted_list = sorted(sorted_list, key=lambda x: x.val)
``````

The run-time by using lambda is 99ms

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