# Three different Python solutions [122ms is fastest]

• 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

• You mean m nodes in each list or m nodes overall? Your stated complexities don't make much sense.

• @StefanPochmann Good point, I've just noticed before reading your message and fixed it.

n is the number of linked lists, m is the "average" number of items per each list, so n * m is the approximate number of total items. Maybe I should have introduced m as the total number of linked list items here...

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.