from operator import attrgetter class Solution: # @param a list of ListNode # @return a ListNode def mergeKLists(self, lists): sorted_list =  for head in lists: curr = head 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 else: return None
To surprise this is much faster than my standard solution.
The time complexity is o(n) in your case. Timesort rocks!
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
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 if sorted_list else None
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.