23题合并k个有序的链表

发表于 | 分类于
本文字数： 1.5k | 阅读时长 ≈ 1 分钟

合并K个有序的链表

难度： hard模式 思路：优先级队列

一、题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

1
2
3
4
5
6
7
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

二、问题分析

首先是hard模式，说明不能轻易的解决这个问题。认真思考了一个小时，觉得已经理清楚思路，然而苦于不知该如何实现自己的思路。试了几种方法，反而是原地打转，于是决定参考一下答案。答案实现了我的思路，原来使用了一种之前没有用过的数据结构，优先级队列(PrivirotyQueue),这一篇专栏简单介绍了优先级队列，对于理解这题，简直是正中靶心。

思路如下：

用三个指针指向k个链表的头部，比较指针中的值，将最小的值加入到结果中，然后指针后移，直到所有的指针为空。由于是列表，无法直接得到所有链表的头部，所以只能通过优先级队列来做。遍历列表，将头指针和头指针的val组成一个元组入队列，出队列时头指针的val作为评判其优先级的标准。注意事项，当队列中的元组优先级(即头指针的val)相同时，将会把指针这个对象作为比较优先级的评判标准，但是对象在python中是不能直接比较的，会引起代码崩溃，元组之间的元素用逗号隔开，不能有空格，否则代码也会崩溃。

三、代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from queue import PriorityQueue as PQ
# 导入优先级队列的包

class Solution:
    def mergeKLists(self, lists):
        head = point = ListNode(0)
        pq = PQ()
        index = 0
        for l in lists:
            if l:
                # 当列表的优先级相同(即val相等）时，由元祖中的第二个元素确定优先级，
                # 而链表是对象不能直接确定优先级，所以加入一个变化的下标作为优先级避免程序崩溃
                pq.put((l.val,index,l))
                index += 1                        
        while not pq.empty():
            val,index, node = pq.get() 
            # 不能直接操作point，会导致链表的断裂
            point.next = node
            point = point.next
            node = node.next
            if node != None:
                pq.put((node.val,index,node))
                index += 1
        return head.next

复杂度分析

O(N log k) :比较大小的时间花费将被减少到O(log k)，因为优先级队列的内部实现机制用到了堆，但是找到最小值的节点仅仅花费 O(1)， 在最终的链表中有K个节点。