您现在的位置是：首页 >技术交流 >python-leetcode-合并 K 个升序链表网站首页技术交流

23. 合并 K 个升序链表 - 力扣（LeetCode）

from heapq import heappush, heappop
from typing import List, Optional
# 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]:
        heap = []
    
        # 把所有链表的头节点加入小顶堆 (值, 索引, 节点)
        for i, node in enumerate(lists):
            if node:
                heappush(heap, (node.val, i, node))  # 加入索引区分相同值
        
        dummy = ListNode()  # 虚拟头节点
        cur = dummy
        
        while heap:
            val, i, node = heappop(heap)  # 取出最小的节点
            cur.next = node
            cur = cur.next
            
            if node.next:
                heappush(heap, (node.next.val, i, node.next))  # 加入下一个节点
        
        return dummy.next