# Three ways to solve this problem in Python (build-in sort, merge and priority queue)

• I figured out that OJ converts Python list into a ListNode automatically, so in my solution I return a list directly(Sorry for my laziness)

The first solution uses Python build-in sort, to my surprise it's the fastest one, although it's kind of a hack:

``````def mergeKLists(lists):
ret = []
for lst in lists:
while lst:
ret.append(lst.val)
lst = lst.next

return sorted(ret)
``````

The second solution uses merge sort:

``````def mergeKLists(lists):

def merge(lst1, lst2):
dummy = pt = ListNode(-1)
while lst1 and lst2:
if lst1.val < lst2.val:
pt.next = lst1
lst1 = lst1.next
else:
pt.next = lst2
lst2 = lst2.next
pt = pt.next

pt.next = lst1 if not lst2 else lst2
return dummy.next

if not lists:
return None

if len(lists) == 1:
return lists[0]
mid = len(lists)/2
left = mergeKLists(lists[:mid])
right = mergeKLists(lists[mid:])

return merge(left, right)
``````

The third one uses priority queue:

``````import heapq
def mergeKLists(lists):

ret, heap = [], []
for lst in lists:
while lst:
heapq.heappush(heap, lst.val)
lst = lst.next

while heap:
ret.append(heapq.heappop(heap))
return ret``````

• Hi, I have a question about second solution. When you divided lists, the left part [:mid], the right part[mid :]. Why the right part couldn’t start at (mid+1)? I think it is similar to the binary search: left [:mid], right[mid + 1:]. Thanks.

• hi there, please think about a list as [ [2,2,2], [1,1,1], [3,3,3] ], if you skipped the middle one, the result would be [2,2,2,3,3,3], which is incorrect obviously, in fact, I think this method should be called divide and conquer rather than binary search :)

• [:mid] means from 0 to mid - 1, that might be the reason why author didn't use [mid +1:] as the second part while divide

• "I figured out that OJ converts Python list into a ListNode automatically"

I think what really happens is that the OJ serializes the result to a string, and both Python lists and ListNode lists look the same when serialized (if they have the same contents).

In any case, I think it's bad to exploit this. It's wrong, and it makes your solutions incomparable to those that do it right.

• thanks for sharing. what's the complexity of heapq version?

• Thanks for sharing. Based on your sort() version, I implemented version that returns linked list rather than array.

``````class Solution(object):
def mergeKLists(self, lists):
res = []
for l in lists:
while l:
res.append((l.val, l))
l = l.next

res.sort(key=lambda tup: tup[0])

dummy = ListNode(None)
cur = dummy

for l in res:
cur.next = l[1]
cur = cur.next

return dummy.next``````

• I think it should be O(N logN).

• I think the third solution's time complexity is quite high.

• @chris.zhang.336 How do we analyze the time complexity of these solutions? In my opinion, the priority queue solution takes O(nlgk), the merge sort solution has the same level of asymptotic time complexity, because n/k * lgk * k = nlgk (each list, whose length is n/k, will be scanned lgk times).

• This heap solution is NlogN and we can do better with a NKlogK solution since K is most likely minimal relative to N.

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