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 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. 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) dummy = ListNode(None) cur = dummy for l in res: cur.next = l cur = cur.next return dummy.next
@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).
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.