```
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if len(lists) == 0:
return None
Solution.mergeSort(self, lists, 0, len(lists) - 1)
return lists[0]
def mergeSort(self, lists, p, r):
if p < r:
q = (p + r) / 2
Solution.mergeSort(self, lists, p, q)
Solution.mergeSort(self, lists, q + 1, r)
Solution.mergeTwoParts(self, lists, p, q, r)
def mergeTwoParts(self, lists, p, q,r ):
node = Solution.mergeTwoLists(self, lists[p], lists[r])
for i in range(p, r + 1):
lists[i] = node
def mergeTwoLists(self, l1, l2):
"""
This function is from Merge Two Sorted Lists.
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if l1 != None and l2 == None:
return l1
elif l1 == None and l2 != None:
return l2
elif l1 == None and l2 == None:
return None
if l1.val < l2.val:
head = l1
else:
head = l2
last = head
while l1 != None and l2 != None:
if l1.val < l2.val:
last, l1 = l1, l1.next
else:
last.next, last, l2.next, l2 = l2, l2, l1, l2.next
if l1 != None:
last.next = l1
else:
last.next = l2
return head
```