当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.023.Merge k Sorted Lists 合并K个排序链表

LeetCode.023.Merge k Sorted Lists 合并K个排序链表

题目描述

23 Merge k Sorted Lists
https://leetcode-cn.com/problems/merge-k-sorted-lists/

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

相似题目

TopK问题
LeetCode.215.Kth Largest Element in an Array 寻找数组中第K大的数
LeetCode.703.Kth Largest Element in a Stream 数据流中的第K大元素
LeetCode.347.Top K Frequent Elements 前K个高频元素
LeetCode.剑指offer.040.数组中最小的k个数
LeetCode.023.Merge k Sorted Lists 合并K个排序链表

归并排序问题
LeetCode.021.Merge Two Sorted Lists 合并两个有序链表
LeetCode.023.Merge k Sorted Lists 合并K个排序链表


解题过程

优先队列/最小堆

归并排序的扩展,普通的归并排序是2路归并,这个是多路归并。每次我们需要从 k 个链表结点中找到最小的加入结果链表,很自然的就想到 TopK 问题中用到的优先队列,也就是最小堆/最大堆。

优先队列插入和删除的复杂度为O(logk),需要进行 N 次,其中 N 是总的结点个数,所以时间复杂度为 O(Nlogk)
优先队列长度不会超过k,所以空间复杂度 O(k)

private static class SolutionV2020 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (null == lists || lists.length < 2) {
            return null == lists || lists.length == 0 ? null : lists[0];
        }
        ListNode dumbHead = new ListNode(0);
        ListNode k = dumbHead;
        // 最小堆
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                priorityQueue.offer(lists[i]);
            }
        }
        while (!priorityQueue.isEmpty()) {
            // 选择堆顶结点即最小结点加入结果链表
            ListNode listNode = priorityQueue.poll();
            k.next = listNode;
            k = k.next;
            // 最小结点所在链表指针后移加入堆中
            if (listNode.next != null) {
                priorityQueue.offer(listNode.next);
            }
        }
        return dumbHead.next;
    }
}

k-1次两两链表归并

分治法:logk次两两合并


GitHub代码

algorithms/leetcode/leetcode/_023_MergeKSortedLists.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_023_MergeKSortedLists.java


上一篇 LeetCode.剑指offer.056.数组中数字出现的次数

下一篇 LeetCode.046.Permutations 全排列

阅读
评论
478
阅读预计2分钟
创建日期 2020-04-26
修改日期 2020-04-26
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论