There are k linked lists, so we will need k indexes. Each time, if we simply
loop on k indexes to find the smallest node, the overall time complexity would
be **O(n * k)**. To reduce the time complexity, we can use a heap to store
current visiting node for each linked list, pop the smallest one and push it's
next node each time. So the overall time complexity would be **O(n * lg(k))**.

```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
import heapq
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
heap = []
for group, head in enumerate(lists):
if head is not None:
heapq.heappush(heap, (head.val, group))
currents = lists[:]
head = ListNode(None)
current = head
while heap:
_, group = heapq.heappop(heap)
node = currents[group]
if node.next:
heapq.heappush(heap, (node.next.val, group))
currents[group] = node.next
node.next = None
current.next = node
current = node
return head.next
```