"""
Merge k sorted linked lists and return it as one sorted list. Analyze and
describe its complexity.
"""
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if lists is None or lists == []:
            return None
        mergeCache = []
        p = ListNode(None)
        q = p
        for key in range(len(lists)):
            if lists[key] is not None:
                heapq.heappush(mergeCache, (lists[key].val, key))
                lists[key] = lists[key].next

        while len(mergeCache) > 0:
            node = heapq.heappop(mergeCache)
            val, key = node[0], node[1]
            q.next = ListNode(val)
            q = q.next
            if lists[key] is not None:
                heapq.heappush(mergeCache, (lists[key].val, key))
                lists[key] = lists[key].next
        return p.next

@@ -516,16 +516,17 @@
   q = p%0A
+%0A
         
@@ -529,19 +529,17 @@
     for 
-key
+i
  in rang
@@ -574,32 +574,18 @@
 f lists%5B
-key%5D is not None
+i%5D
 :%0A      
@@ -632,68 +632,19 @@
 sts%5B
-key
+i
 %5D.val, 
-key))%0A                lists%5Bkey%5D = lists%5Bkey%5D.next
+i))
 %0A%0A  
@@ -655,20 +655,16 @@
   while 
-len(
 mergeCac
@@ -669,13 +669,8 @@
 ache
-) %3E 0
 :%0A  
@@ -679,20 +679,27 @@
         
-node
+val, head_i
  = heapq
@@ -735,34 +735,29 @@
     
-val, key = node%5B0%5D, node%5B1
+q.next = lists%5Bhead_i
 %5D%0A  
@@ -769,49 +769,61 @@
     
+ q =
  q.next
- = ListNode(val)%0A            q = q
+%0A            lists%5Bhead_i%5D = lists%5Bhead_i%5D
 .nex
@@ -849,24 +849,15 @@
 sts%5B
-key%5D is not None
+head_i%5D
 :%0A  
@@ -908,68 +908,30 @@
 sts%5B
-key
+head_i
 %5D.val, 
-key))%0A                lists%5Bkey%5D = lists%5Bkey%5D.next
+head_i))%0A
 %0A   

modify 023, no longer rebuild nodes