LeetCode23 合并K个有序链表

问题描述

合并k个有序链表，返回合并后的排序链表。

解题思路

本题是LeetCode第21题-合并两个有序链表的扩展。所以，一种思路是采用两两合并的算法进行合并，但是算法复杂度较高。
另外一种思路是采用最小堆法，算法步骤如下：

将k个链表的头结点放入最小堆；
从堆中取出最小元素并插入结果链表中;
如果取出的最小元素还有下一个元素，将其放入最小堆中;
执行步骤2，直到堆中元素全部被取出。

代码


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        import heapq

	# 初始化返回的链表
        head = ListNode(0)
        p = head

	# 初始化最小堆：取链表的头节点
        heap = []
        for i in range(len(lists)):
            n = lists[i]
            if not n:
                continue
	    # 注意ListNode对象不能应用<或者>运算符，所以引入链表下标。通过(n.val, i)即可完成元素比较。
            heapq.heappush(heap, (n.val, i, n)) 

	# 每次取出堆中最小的元素，插入到返回链表中，然后再将下一个节点插入最小堆中
        while heap:
            _, i, min_node = heapq.heappop(heap)
            p.next = min_node
            p = min_node
            if min_node.next:
                heapq.heappush(heap, (min_node.next.val, i, min_node.next))
        return head.next

问题描述

解题思路

代码

推荐文章（由hexo文章推荐插件驱动）