面试算法78:合并排序链表

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

题目

输入k个排序的链表,请将它们合并成一个排序的链表。
面试算法78:合并排序链表,算法,面试,算法,链表

分析:利用最小堆选取值最小的节点

用k个指针分别指向这k个链表的头节点,每次从这k个节点中选取值最小的节点。然后将指向值最小的节点的指针向后移动一步,再比较k个指针指向的节点并选取值最小的节点。重复这个过程,直到所有节点都被选取出来。

public class Test {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(6);
        ListNode listNode7 = new ListNode(7);
        ListNode listNode8 = new ListNode(8);
        ListNode listNode9 = new ListNode(9);

        listNode1.next = listNode4;
        listNode4.next = listNode7;

        listNode2.next = listNode5;
        listNode5.next = listNode8;

        listNode3.next = listNode6;
        listNode6.next = listNode9;

        ListNode[] lists = {listNode1, listNode2, listNode3};
        ListNode result = mergeKLists(lists);
        while (result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);
        for (ListNode list : lists) {
            if (list != null) {
                minHeap.offer(list);
            }
        }

        while (!minHeap.isEmpty()) {
            ListNode least = minHeap.poll();
            cur.next = least;
            cur = least;

            if (least.next != null) {
                minHeap.offer(least.next);
            }
        }

        return dummy.next;
    }
}

分析:按照归并排序的思路合并链表

输入的k个排序链表可以分成两部分,前k/2个链表和后k/2个链表。如果将前k/2个链表和后k/2个链表分别合并成两个排序的链表,再将两个排序的链表合并,那么所有链表都合并了。合并k/2个链表与合并k个链表是同一个问题,可以调用递归函数解决。文章来源地址https://www.toymoban.com/news/detail-772842.html

public class Test {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(6);
        ListNode listNode7 = new ListNode(7);
        ListNode listNode8 = new ListNode(8);
        ListNode listNode9 = new ListNode(9);

        listNode1.next = listNode4;
        listNode4.next = listNode7;

        listNode2.next = listNode5;
        listNode5.next = listNode8;

        listNode3.next = listNode6;
        listNode6.next = listNode9;

        ListNode[] lists = {listNode1, listNode2, listNode3};
        ListNode result = mergeKLists(lists);
        while (result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }

        return mergeLists(lists, 0, lists.length);
    }

    private static ListNode mergeLists(ListNode[] lists, int start, int end) {
        if (start + 1 == end) {
            return lists[start];
        }

        int mid = (start + end) / 2;
        ListNode head1 = mergeLists(lists, start, mid);
        ListNode head2 = mergeLists(lists, mid, end);
        return merge(head1, head2);
    }

    private static ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                cur.next = head1;
                head1 = head1.next;
            }
            else {
                cur.next = head2;
                head2 = head2.next;
            }

            cur = cur.next;
        }
        cur.next = head1 == null ? head2 : head1;
        return dummy.next;
    }
}

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

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

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

相关文章

  • 《剑指offer》——合并两个排序的链表

    本期给大家带来的是  合并两个排序的链表 这道题的讲解!!!  接下来,我们还是先从题干的内容入手,先分析一波题目,在进行画图思考操作。 💨  题目如下: 示例1 输入:{1,3,5},{2,4,6} 返回值:{1,2,3,4,5,6} 示例2 输入:{},{} 返回值:{} 示例3 输入:{-1,2,4},{1,3,4} 返回值:

    2023年04月13日
    浏览(36)
  • (链表) 剑指 Offer 25. 合并两个排序的链表 ——【Leetcode每日一题】

    难度:简单 输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。 示例1: 输入:1-2-4, 1-3-4 输出:1-1-2-3-4-4 限制 : 0 = 链表长度 = 1000 注意:本题与 21. 合并两个有序链表 相同 💡思路: 法一:递归 将该问题可以分解成子链表,只比较当前 l1 链

    2024年02月15日
    浏览(46)
  • 【Leetcode -21.合并两个有序链表 -83.删除排序链表中的重复元素】

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

    2023年04月24日
    浏览(49)
  • 【C/C++练习】合并k个已排序的链表

    前言:  今天给大家分享一道面试中常见的题目——合并K个升序链表,我会用暴力和分治两钟方法去求解这道题目,通过动图展示问题求解的全过程。这里提醒大家,画图是我们求解复杂问题的有效手段,有时可以起到事半功倍的效果,各位小伙伴在做题的过程中如果遇到

    2024年02月09日
    浏览(40)
  • 面试热题(合并K个升序链表)

    给定一个链表数组,每个链表都已经按升序排列。 请将所有链表合并到一个升序链表中,返回合并后的链表。        这道题看似困难题,其实还是比较容易好想的,我们可以维护一个优先最小队列,然后声明一个虚拟头结点,每次出一个最小的节点挂载在已经挂载节点的后

    2024年02月12日
    浏览(33)
  • LeetCode150道面试经典题-- 合并两个有序链表(简单)

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例 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月12日
    浏览(40)
  • Java 算法篇-链表的经典算法:有序链表去重、合并多个有序链表

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍         文章目录          1.0 链表的说明          2.0 有序链表去重的实现方式         2.1 有序链表去重(保留重复的节点) - 使用递归来实现         2.2 有序链表去重(保留重复的节点) - 使用双指针

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

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

    2024年02月22日
    浏览(51)
  • 算法重温:排序 —— 合并排序

    目录 1. 基本思想 2. 排序原理 3. 排序过程 4.复杂度分析 5.代码实现 (C++、java) 6.运行结果 7.各排序算法效率 通过一趟排序将待排序列分割成两部分,其中一部分记录的均比另一部分记录的小。之后分别对这两部分记录继续进行排序,以达到整个序列有序的目的。

    2024年02月07日
    浏览(71)
  • 排序算法-合并排序法(MergeSort)

    合并排序法(MergeSort)是针对已排序好的两个或两个以上的数列(或数据文件),通过合并的方式将其组合成一个大的且已排好序的数列(或数据文件),步骤如下: 将个长度为1的键值成对地合并成个长度为2的键值组。 将个长度为2的键值组成对地合并成个长度为4的键值组

    2024年02月07日
    浏览(71)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包