```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param {ListNode[]} lists
# @return {ListNode}
def mergeKLists(self, lists):
if not lists:
return None
l = len(lists)
if l == 1:
return lists[0]
mid = l//2
return self.mergeLists(self.mergeKLists(lists[:mid]),self.mergeKLists(lists[mid:]))
def mergeLists(self, list1, list2):
p, q = list1, list2
head = tail = None
while p and q:
if p.val < q.val:
if not tail:
head = p
tail = p
p = p.next
else:
tail.next = p
tail = tail.next
p = p.next
else:
if not tail:
head = q
tail = q
q = q.next
else:
tail.next = q
tail = tail.next
q = q.next
if p:
if not tail:
head = p
tail = p
else:
tail.next = p
if q:
if not tail:
head = q
tail = q
else:
tail.next = q
if not tail:
return None
else:
return head
```