合并 K 个升序链表[困难]

这篇具有很好参考价值的文章主要介绍了合并 K 个升序链表[困难]。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目

给你一个链表数组,每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:[ 1->4->5, 1->3->4, 2->6 ]
将它们合并到一个有序链表中得到1->1->2->3->4->4->5->6

示例 2:
输入:lists = []
输出:[]

示例 3:
输入:lists = [[]]
输出:[]

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i]按 升序 排列
lists[i].length的总和不超过10^4

二、代码

合并两个有序链表: 在解决「合并K个排序链表」这个问题之前,我们先来看一个更简单的问题:如何合并两个有序链表?假设链表ab的长度都是n,如何在O(n)的时间代价以及O(1)的空间代价完成合并? 这个问题在面试中常常出现,为了达到空间代价是O(1),我们的宗旨是「原地调整链表元素的next指针完成合并」。以下是合并的步骤和注意事项,对这个问题比较熟悉的读者可以跳过这一部分。此部分建议结合代码阅读。
【1】首先我们需要一个变量head来保存合并之后链表的头部,你可以把head设置为一个虚拟的头(也就是headval属性不保存任何值),这是为了方便代码的书写,在整个链表合并完之后,返回它的下一位置即可。
【2】我们需要一个指针tail来记录下一个插入位置的前一个位置,以及两个指针aPtrbPtr来记录ab未合并部分的第一位。注意这里的描述,tail不是下一个插入的位置,aPtrbPtr所指向的元素处于「待合并」的状态,也就是说它们还没有合并入最终的链表。 当然你也可以给他们赋予其他的定义,但是定义不同实现就会不同。
【3】当aPtrbPtr都不为空的时候,取val属性较小的合并;如果aPtr为空,则把整个bPtr以及后面的元素全部合并;bPtr为空时同理。
【4】在合并的时候,应该先调整tailnext属性,再后移tail*Ptr或者bPtr。那么这里tail*Ptr是否存在先后顺序呢?它们谁先动谁后动都是一样的,不会改变任何元素的next指针。

public ListNode mergeTwoLists(ListNode a, ListNode b) {
    if (a == null || b == null) {
        return a != null ? a : b;
    }
    ListNode head = new ListNode(0);
    ListNode tail = head, aPtr = a, bPtr = b;
    while (aPtr != null && bPtr != null) {
        if (aPtr.val < bPtr.val) {
            tail.next = aPtr;
            aPtr = aPtr.next;
        } else {
            tail.next = bPtr;
            bPtr = bPtr.next;
        }
        tail = tail.next;
    }
    tail.next = (aPtr != null ? aPtr : bPtr);
    return head.next;
}

时间复杂度: O(n)
空间复杂度: O(1)

【1】顺序合并: 我们可以想到一种最朴素的方法:用一个变量ans来维护以及合并的链表,第i次循环把第i个链表和ans合并,答案保存到ans中。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}

时间复杂度: 假设每个链表的最长长度是n。在第一次合并后,ans的长度为n;第二次合并后,ans的长度为2×n,第i次合并后,ans的长度为i×n。第i次合并的时间代价是O(n+(i−1)×n)=O(i×n),那么总的时间代价为O(∑i=1k(i×n))=O(((1+k)⋅k)/2×n)=O(k^2n),故渐进时间复杂度为O(k^2 n)
空间复杂度: 没有用到与kn规模相关的辅助空间,故渐进空间复杂度为O(1)

【2】分治合并: 考虑优化方法一,用分治的方法进行合并。
1、将k个链表配对并将同一对中的链表合并;
2、第一轮合并以后,k个链表被合并成了k/2个链表,平均长度为2n/k​,然后是k/4个链表,k/8个链表等等;
3、重复这一过程,直到我们得到了最终的有序链表。

合并 K 个升序链表[困难],算法题,链表,数据结构,算法,java,后端,面试,spring

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}

时间复杂度: 考虑递归「向上回升」的过程——第一轮合并k/2组链表,每一组的时间代价是O(2n);第二轮合并k/4组链表,每一组的时间代价是O(4n)…所以总的时间代价是O(∑i=1∞k/2^i×2^in)=O(kn×log⁡k),故渐进时间复杂度为O(kn×log⁡k)
空间复杂度: 递归会使用到O(log⁡k)空间代价的栈空间。

【3】使用优先队列合并: 这个方法和前两种方法的思路有所不同,我们需要维护当前每个链表没有被合并的元素的最前面一个,k个链表就最多有k个满足这样条件的元素,每次在这些元素里面选取val属性最小的元素合并到答案中。在选取最小元素的时候,我们可以用优先队列来优化这个过程。

class Solution {
    class Status implements Comparable<Status> {
        int val;
        ListNode ptr;

        Status(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }

        public int compareTo(Status status2) {
            return this.val - status2.val;
        }
    }

    PriorityQueue<Status> queue = new PriorityQueue<Status>();

    public ListNode mergeKLists(ListNode[] lists) {
        for (ListNode node: lists) {
            if (node != null) {
                queue.offer(new Status(node.val, node));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!queue.isEmpty()) {
            Status f = queue.poll();
            tail.next = f.ptr;
            tail = tail.next;
            if (f.ptr.next != null) {
                queue.offer(new Status(f.ptr.next.val, f.ptr.next));
            }
        }
        return head.next;
    }
}

时间复杂度: 考虑优先队列中的元素不超过k个,那么插入和删除的时间代价为O(log⁡k),这里最多有kn个点,对于每个点都被插入删除各一次,故总的时间代价即渐进时间复杂度为O(kn×log⁡k)
空间复杂度: 这里用了优先队列,优先队列中的元素不超过k个,故渐进空间复杂度为O(k)文章来源地址https://www.toymoban.com/news/detail-787947.html

到了这里,关于合并 K 个升序链表[困难]的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析)

    还不清楚链表的码喵们可以看看前篇关于链表的详解 既然已经懂得了链表该如何实现,那么现在就趁热打铁开始练习!这里给码喵们整理了相对不错的一些OJ题来练习  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 思路:遍历整个表,访问每个表的值并且删除再将nex

    2024年02月22日
    浏览(48)
  • 数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样,但本文并未采用 #define 定义容量的写法,这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟,后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中,重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(60)
  • 【数据结构与算法】 合并排序

    CSDN话题挑战赛第1期 活动详情地址:https://marketing.csdn.net/p/bb5081d88a77db8d6ef45bb7b6ef3d7f 参赛话题:Java学习记录 话题描述:可以记录一下平时学习Java中的一些知识点、心得、例题、常见的问题解决 好文推荐🔥图文并茂详解十大排序算法让您回味无穷 合并排序是建立在归并操作

    2024年02月02日
    浏览(40)
  • C语言---数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样,但本文并未采用 #define 定义容量的写法,这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟,后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中,重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(67)
  • 数据结构:两个顺序表合并算法

            将a,b两个有序顺序表进行合并,放在c顺序表当中,并且要保证顺序表c仍然有序。         因为a,b两个顺序表是有序的,所有可以从前往后一起查找a,b当中最小的一个数值,放入到c中。         如果遍历到最后,a遍历完了,b没有遍历完,就把b剩下的放入

    2024年02月08日
    浏览(38)
  • 合并 k 个升序的链表

    C++——优先级队列(priority_queue)_c++priority_queue__好好学习的博客-CSDN博客 那么这道题就可以用小顶堆 分治的思想,归并排序的思想

    2024年02月10日
    浏览(48)
  • 【算法与数据结构】链表

    链表是由一串节点串联在一起的,链表的每个节点存储两个信息:数据+下一个节点的地址 分清楚两个概念:什么是内存内部,什么是程序内部 内存内部: 信息存储在内存空间里的 程序内部: 通过什么信息,去操作结构 如果想操作链表的话,我们依靠的是程序内部的信息,

    2024年02月03日
    浏览(44)
  • 【数据结构与算法】链表

    对于顺序表存在一些缺陷: 中间/头部的插入删除,时间复杂度为O(N) 。头部插入需要挪动后面的元素 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插

    2023年04月09日
    浏览(44)
  • 合并两个有序链表,将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    题记: 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入 :l1 = [1,2,4], l2 = [1,3,4] 输出 :[1,1,2,3,4,4] 示例 2: 输入 :l1 = [], l2 = [] 输出 :[] 示例 3: 输入 :l1 = [], l2 = [0] 输出 :[0] 提示: 两个链表的节点数

    2024年02月07日
    浏览(63)
  • 02-链表 (数据结构和算法)

    3.1 链表的基本概念 前面我们在学习顺序表时,线性表的顺序存储结构的特点是逻辑关系上相邻的两个数据元素在物理位置上也是相邻的。我们会发现虽然顺序表的查询很快,时间复杂度为O(1),但是增删的效率是比较低的,因为每一次增删操作都伴随着大量的数据元素移动。为

    2024年02月16日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包