Python solution in 122ms:

```
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
For n linked lists of m nodes:
Time: O(n * m * log(n * m))
Space: O(n * m)
"""
def walk(node):
while node:
yield node.val
node = node.next
a = []
for node in lists:
a.extend(walk(node))
a.sort()
head = node = ListNode(None)
for v in a:
node.next = ListNode(v)
node = node.next
return head.next
```

The above is more "Pythonic" and uses as much of the standard library functionality as possible. This is why it has reasonable speed at the cost of some extra memory consumption.

Your interviewer will likely be more interested in the following solution:

```
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
For n linked lists of m nodes:
Time: O(n**2 * m)
Space: O(n * m)
"""
head = tail = None
lists = [node for node in lists if node is not None]
values = [node.val for node in lists if node is not None]
while lists:
min_val = min(values)
if head is None:
head = tail = ListNode(min_val)
else:
tail.next = ListNode(min_val)
tail = tail.next
idx = values.index(min_val)
next = lists[idx].next
if next is None:
del lists[idx]
del values[idx]
else:
lists[idx] = next
values[idx] = next.val
return head
```

This is slow [1400ms], since fine grained logic is expressed in Python.

Another solution would be to copy all values into a heap, then construct the resulting linked list from that:

```
# See: https://docs.python.org/2/library/heapq.html
from heapq import heappush, heappop
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
For n linked lists of m nodes:
Time: O(n * m * log(n * m))
Space: O(n * m)
"""
# Max-heap
heap = []
# Copy all values into the heap
for node in lists:
while node is not None:
heappush(heap, node.val)
node = node.next
# Construct linked list from heap values
head = node = ListNode(None)
while heap:
node.next = ListNode(heappop(heap))
node = node.next
return head.next
```

It runs in 166ms