Leetcode 23. Merge K ascending linked lists

Topic link ：https://leetcode.cn/problems/merge-k-sorted-lists/

Title Description

Here's an array of linked lists , Each list has been listed in ascending order . Please merge all the linked lists into one ascending list , Return the merged linked list .

 Example  1：
 Input ：lists = [[1,4,5],[1,3,4],[2,6]]
 Output ：[1,1,2,3,4,4,5,6]
 explain ： The linked list array is as follows ：
[
  1->4->5,
  1->3->4,
  2->6
]
 Combine them into an ordered list to get .
1->1->2->3->4->4->5->6

 Example  2：
 Input ：lists = []
 Output ：[]

 Example  3：
 Input ：lists = [[]]
 Output ：[]

This question is obviously an array k Expansion of road merging , And arrays k There are three solutions to path merging （ hypothesis k The number of all elements of the path array is n）：
（1）k Copy the path array to the same array , And then sort them uniformly
（2）k Path array k Subordination
（3） Use the minimum heap , Successively k Minimum value found in arrays , repeat n Time
And this problem changes the array into a linked list , Then it is more appropriate to use the third method .

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        k = len(lists)
        dummy = ListNode(val=-1)
        tail = dummy
        heap = []
        # put each list head to min heap
        for i, node in enumerate(lists):
            if node is not None:
                heap.append((node.val, i, node))  #  When val The same pass link_index:i Compare 
        heapq.heapify(heap)
        # find min node n times
        while len(heap) > 0:
            _, idx, cur_node = heapq.heappop(heap)
            tail.next = cur_node
            tail = cur_node
            if cur_node.next is not None:
                heapq.heappush(heap, (cur_node.next.val, idx, cur_node.next))
        return dummy.next