# Heap based Python solution

• ``````class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
from heapq import heappush, heappop

# using a heap , find the minimum of the list heads,

if lists is None or len(lists) == 0:
return None

nlen = len(lists)
if nlen == 1:
return lists[0]

# { l1, l2 , ... lk}
heap = []
for x in xrange(nlen):
lnode = lists[x]
if lnode is not None:
heappush(heap, (lnode.val, lnode.next))

result = None
temp = None
prev = None

while len(heap) != 0:

(val, node) = heappop(heap)
if result is None:
result = ListNode(val)
result.next = None
prev = result
else:
temp = ListNode(val)
prev.next = temp
prev = temp

if temp is not None:
temp = temp.next

if node is not None:
heappush(heap, (node.val, node.next))

return result
``````

• Hi,

Thanks for your posting, I have a question, why do you need to move temp to next, such as,
if temp is not None:
temp = temp.next

I cannot find out this makes any sense.
Thank you very much

• @zhang57

For the following iteration of the while loop, we will probably run the "else:" case.
Which means we're setting the temp node.
Since this temp node was the temp.next from last iteration, we're esentially setting the next node in the list.
Otherwise, we'd constantly be overwriting the temp node (and never setting its next pointer)

• Hi zhang57,

Consider the very first scenario when result is None. At that instance, we initialize result with just the first popped node. In the second iteration , we initialize temp with popped value and we need to move to next in order to make it available for the next popped node (in the next iteration)

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