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
```