Sui Xin's Blog

[LeetCode]23. 合并K个排序链表（Merge k Sorted Lists）

Posted on In Disqus:

题目描述

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

示例:

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

解题思路

  1. 解法一：优先队列。使用优先队列将现有 list 中的所有存起来，保存两个信息：(值， 索引)，因为如果直接保存链表节点，优先队列内部比较大小时会报错。
  2. 解法二：归并。类似于归并排序，合并两个链表时使用递归的方式！

代码

Python 3.6

解法一：优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        from queue import PriorityQueue
        
        dummy = cur = ListNode(-1)
        q = PriorityQueue()
        for idx, node in enumerate(lists):
            if node is not None:
                # 存储 node 的值和索引，如果直接存储 node，则因为比较大小而报错
                q.put((node.val, idx))
                lists[idx] = lists[idx].next
                
        while not q.empty():
            val, idx = q.get()
            cur.next = ListNode(val)
            cur = cur.next
            if lists[idx] is not None:
                q.put((lists[idx].val, idx))
                lists[idx] = lists[idx].next
        return dummy.next

执行用时 : 232 ms
内存消耗 : 17.3 MB

解法二：归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists:
            return
        length = len(lists)
        if length == 1:
            return lists[0]
        mid = length // 2
        left, right = self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:])
        return self.merge2lists(left, right)
    
    def merge2lists(self, left, right):
        if not left:
            return right
        if not right:
            return left
        if left.val <= right.val:
            left.next = self.merge2lists(left.next, right)
            return left
        else:
            right.next = self.merge2lists(left, right.next)
            return right

执行用时 : 296 ms
内存消耗 : 26 MB

参考

https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/leetcode-23-he-bing-kge-pai-xu-lian-biao-by-powcai

Related Posts