LeetCode23.合并K个升序链表

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

题目

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 :

输入: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

思路

要将多个已按升序排列的链表合并成一个升序链表,可以使用分治法的思想。我们利用分治法的思想,递归地将链表数组拆分成两部分,然后合并这些部分,最终得到一个合并后的升序链表。

  • 定义一个辅助函数mergeTwoLists(ListNode* list1, ListNode* list2),用于合并两个链表的方法,这是我们之前讨论过的合并两个升序链表的方法。

  • 在mergeKLists函数中,首先判断输入的链表数组是否为空,如果为空则返回nullptr。

  • 利用分治法的思想,将链表数组不断地拆分成两部分,然后递归地合并这些部分,直到只剩下一个链表为止。具体步骤如下:

    • 计算链表数组的中间位置mid,将链表数组拆分成两部分:左半部分为[0, mid-1],右半部分为[mid, size-1]。
    • 递归调用mergeKLists函数,分别对左右两部分进行合并,得到leftList和rightList。
    • 最终,再调用mergeTwoLists方法将leftList和rightList合并为一个新的升序链表,并返回合并后的结果。
  • 最终返回合并后的链表即可。文章来源地址https://www.toymoban.com/news/detail-834094.html

Code:

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) {
            return nullptr;
        }
        return merge(lists, 0, lists.size() - 1);
    }

private:
    ListNode* merge(vector<ListNode*>& lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        if (left < right) {
            int mid = left + (right - left) / 2;
            ListNode* leftList = merge(lists, left, mid);
            ListNode* rightList = merge(lists, mid + 1, right);
            return mergeTwoLists(leftList, rightList);
        }
        return nullptr;
    }

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1) {
            return list2;
        }
        if (!list2) {
            return list1;
        }
        
        if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

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

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

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

相关文章

  • 23. 合并 K 个升序链表(递归分治)

    这是我的第一个自己ak的分治题目!!!好耶!!(骄傲脸 思路参考:148. 排序链表(归并排序)

    2024年01月16日
    浏览(31)
  • 【力扣每日一题】23. 合并 K 个升序链表 &暴力法-快排 & 8.12打卡

    合并 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 ] 将它们合并到一个有序

    2024年02月13日
    浏览(34)
  • 2023-08-12 LeetCode每日一题(合并 K 个升序链表)

    点击跳转到题目位置 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 示例 1: 示例 2: 示例 3:

    2024年02月13日
    浏览(39)
  • 合并 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: 输入

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

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

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

    题记: 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 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日
    浏览(62)
  • 面试热题(合并K个升序链表)

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

    2024年02月12日
    浏览(31)
  • 【力扣每日一题】2023.8.12 合并K个升序链表

    目录 题目: 示例: 分析: 代码: 题目给我们一个链表数组,数组里的链表都是升序的,让我们合并这些链表,要求合并之后还是升序的。 最简单最直观的做法就是遍历整个数组,把每个链表的节点都取出来塞到一个容器里,然后对容器进行升序排序,接着按顺序重新串连

    2024年02月13日
    浏览(40)
  • Leetcode算法递归类—合并两个有序链表

    目录 21. 合并两个有序链表 题解: 代码: 将两个升序链表合并为一个新的  升序  链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例 1: 示例 2: 示例 3: 提示: 两个链表的节点数目范围是  [0, 50] -100 = Node.val = 100 l1  和  l2  均按  非递减顺序  

    2024年02月13日
    浏览(38)
  • 【数据结构】--oj_合并两个有序链表(详解)

    目录 方法一:无头结点的方法  方法二:有头结点的方法 题述: 已给函数头: struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) 已给出链表的结构体定义: struct ListNode {     struct ListNode* next;     int val; }; 已知l1、l2分别指向两个链表 要求: 将两个升序链表合并为一

    2024年02月07日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包