[Leetcode][python]Merge k Sorted Lists/合并K个排序链表

àì夳堔傛蜴生んèń 2022-06-09 09:57 176阅读 0赞

## 题目大意 ##

将k个排序好的链表合并成新的有序链表

## 解题思路 ##

堆和分治法

## 代码 ##

### 最小堆方法 ###

用一个大小为K的最小堆（用优先队列+自定义降序实现）(优先队列就是大顶堆，队头元素最大,自定义为降序后，就变成小顶堆，队头元素最小)，先把K个链表的头结点放入堆中，每次取堆顶元素，然后将堆顶元素所在链表的下一个结点加入堆中。

class Solution(object):
        def mergeKLists(self, lists):
            """
            :type lists: List[ListNode]
            :rtype: ListNode
            """
            heap = []
            for node in lists:
                if node: 
                    heap.append((node.val, node))  # 堆中放入tuple：值，地址
            heapq.heapify(heap)  # 做成堆
            dummy = ListNode(0)
            curr = dummy
    
            while heap:
                pop = heapq.heappop(heap)  # 从堆中取最小的值
                curr.next = ListNode(pop[0])  # 将值放入
                curr = curr.next
                if pop[1].next:  # 如果该链表没结束
                    heapq.heappush(heap, (pop[1].next.val, pop[1].next)) # 将该链表下个节点压入栈中
            return dummy.next

## 分治法 ##

利用归并排序的思想，利用递归和分治法将链表数组划分成为越来越小的半链表数组，再对半链表数组排序，最后再用递归步骤将排好序的半链表数组合并成为越来越大的有序链表。

这里就需要用到分治法 Divide and Conquer Approach。简单来说就是不停的对半划分，比如k个链表先划分为合并两个k/2个链表的任务，再不停的往下划分，直到划分成只有一个或两个链表的任务，开始合并。举个例子来说比如合并6个链表，那么按照分治法，我们首先分别合并1和4,2和5,3和6。这样下一次只需合并3个链表，我们再合并1和3，最后和2合并就可以了。

## 总结 ##

关于堆，理解的不是很透彻，可以参考以下两个文章继续学习：  
[http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/][http_bubkoo.com_2014_01_14_sort-algorithm_heap-sort]  
[https://github.com/qiwsir/algorithm/blob/master/heapq.md][https_github.com_qiwsir_algorithm_blob_master_heapq.md]

[http_bubkoo.com_2014_01_14_sort-algorithm_heap-sort]: http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/
[https_github.com_qiwsir_algorithm_blob_master_heapq.md]: https://github.com/qiwsir/algorithm/blob/master/heapq.md