class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
from heapq import heappush, heappop
# might need to use heap, start with k heads of lists
# using a heap , find the minimum of the list heads,
#add it to list advance by next node
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
Heap based Python solution


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)