Leetcodeアルゴリズム——23、複数のチェーンテーブルを結合する

k個の秩序チェーンテーブルを結合し、新しい秩序チェーンテーブルを返します.
例:Input:[1->4->5,1->3->4,2->6]Output:1->1->2->3->4->4->5->6
構想
集計ソートを使用すると、Leetcodeアルゴリズムである21、2つの順序付きチェーンテーブルのマージと同様の考え方になります.
k個のポインタを維持し、k個の数の最小数を抽出するたびに、このポインタ+1をループします.
優先キュー(最小スタック)を用いて,抽出されるたびに最小数の複雑度をO(k)からO(logk)に変える.
全体時間複雑度はO(nlogk)であった.
python実装

class ListNode:
    def __init__(self, x):
        
        if isinstance(x, list):
            self.val = x[0]
            self.next = None
            head = self
            for i in range(1, len(x)):
                head.next = ListNode(x[i])
                head = head.next
        else:
            self.val = x
            self.next = None
        
    def output(self):
        '''
            
        '''
        result = str(self.val)
        head = self.next
        while(head is not None):
            result += f' -> {head.val}'
            head = head.next
        return '(' + result + ')'
    
    
def mergeKLists(lists):
    """
    :type lists: list[ListNode]
    :rtype: ListNode
         
    """
    from queue import PriorityQueue
    
    #        
    head = ListNode(0)
    p = head
    
    #                 
    q = PriorityQueue()
    for l in lists:
        if l:
            q.put((l.val, id(l), l))
            #     id(l)              ，  l.val  ，         。
            #         l，    ，  ListNode            
            #  id(l)  l     ，int ，            id     。
    
    #            
    while(not q.empty()):
        val, _, node = q.get()
        p.next = ListNode(val)
        p = p.next
        node = node.next
        if node:
            q.put((node.val, id(node), node))
    return head.next

if '__main__' == __name__:
    lists = []
    lists.append(ListNode([1,4,5]))
    lists.append(ListNode([1,3,4]))
    lists.append(ListNode([2,6]))
    print(mergeKLists(lists).output())