```
def mergeKLists(self, lists):
lists = [list for list in lists if list]
if not lists:
return None
lis = []
for head in lists:
while head is not None:
lis.append(head.val)
head = head.next
lis.sort()
dummyHead = ListNode(0)
p = dummyHead
for val in lis:
p.next = ListNode(val)
p = p.next
return dummyHead.next
```

I think the time complexity of above solution is O(nk log(nk)). Since sort( ) takes O(nlog(n)) time according to https://wiki.python.org/moin/TimeComplexity

And this solution actually takes 136ms.

While the divide and conquer approach as following:

```
`def mergeKLists(self, lists):
lists = [list for list in lists if list]
if not lists:
return None
end = len(lists) - 1
while end > 0:
begin = 0
while begin < end:
lists[begin] = self.merge(lists[begin], lists[end])
begin += 1
end -= 1
return lists[0]
def merge(self, lis1, lis2):
dummyHead = ListNode(0)
p = dummyHead
while lis1 and lis2:
if lis1.val < lis2.val:
p.next = lis1
p = p.next
lis1 = lis1.next
else:
p.next = lis2
p, lis2 = p.next, lis2.next
if lis1: p.next = lis1
if lis2: p.next = lis2
return dummyHead.next`
```

should be O(nk log(k)), actually takes 504ms.

I'm confused about the time efficiency comparison, why the first solution is way faster than the second solution when its time complexity is larger?