[Leetcode]23. Merge k Sorted Lists @python

タイトル
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
テーマの要件
k個の秩序あるリストを大きなシーケンステーブルに組み合わせ,実現の複雑さを解析した.
問題を解く構想.
この問題はkitt blogを参照し,小根スタック構造を用いて実現する.すべてのリストを最初の要素のサイズでルートスタックに配置し、最小の要素のリストを取り戻すたびに、リストの次の要素をルートスタックに配置します.小根が空になるまで.これにより、順序付けされたリストが得られます.小根スタック構築の複雑度はO(Nlogn)であり,最小値をとるたびに複雑度はO(logn)であり,小根スタックに要素を追加する複雑度はO(logn)である.全実装の複雑さはO(Nlogn)であった.今回の実装ではPythonが提供する小根スタックの構造を直接使用した.
heapq使用説明
aは一般リスト-heapqである.heapify(a)は、最小スタック-heapqを満たすようにaを調整する.heapppop(a)は最小スタックから最小要素-heapqをポップアップする.heappush(a,b)は最小スタックに新しい元素を圧入する
コード#コード#

# 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
        """
        heap = []
        for l in lists:
            if l != None:
                heap.append((l.val,l))
        heapq.heapify(heap)
        dummy = ListNode(0)
        cur = dummy
        while heap:
            _,h = heapq.heappop(heap)
            cur.next = h
            cur = cur.next
            if h.next:
                heapq.heappush(heap,(h.next.val,h.next))
        return dummy.next