合并 k 个升序的链表

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

C++——优先级队列(priority_queue)_c++priority_queue__好好学习的博客-CSDN博客

#include<iostream>
using namespace std;
#include<stack>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<queue>

struct cmp
{
	bool operator()(int x, int y)
	{
		return x > y;//后面的优先级高,所以返回小顶堆,队头元素永远是最小的
	}
};

int main()
{
	priority_queue<int, vector<int>, cmp >pq;
	pq.push(5);
	pq.push(2);
	pq.push(6);
	pq.push(4);
	while (!pq.empty())
	{
		cout << pq.top() << endl;//输出 2 4 5 6
		pq.pop();
	}
	cout << "******" << endl;
	priority_queue<int>pq1;输出 600 500 400 200
	pq1.push(500);
	pq1.push(200);
	pq1.push(600);
	pq1.push(400);
	while (!pq1.empty())
	{
		cout << pq1.top() << endl;
		pq1.pop();
	}
	system("pause");
	return 0;
}
	

那么这道题就可以用小顶堆

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <queue>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return ListNode类
     */

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        class MyCompare {
          public:
            bool operator()(ListNode* a, ListNode* b) {
                return a->val > b->val;
            }
        };
        priority_queue<ListNode*, vector<ListNode*>, MyCompare>pq;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != nullptr)
                pq.push(lists[i]);
        }
        ListNode* res = new ListNode(0);
        ListNode* cur = res;
        ListNode* tmp = nullptr;
        while (!pq.empty()) {
            tmp = pq.top();
            pq.pop();
            cur->next = tmp;
            cur = cur->next;
            if (tmp->next != nullptr) {
                pq.push(tmp->next);
            }
        }
        return res->next;
    }
};

分治的思想,归并排序的思想文章来源地址https://www.toymoban.com/news/detail-686906.html

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    //两个有序链表合并函数
    
    
    //划分合并区间函数
    ListNode* divideMerge(vector<ListNode *> &lists, int left, int right){ 
        if(left == right) 
            return lists[left];
        //从中间分成两段,再将合并好的两段合并
        int mid = (left + right) / 2; 
        ListNode*pHead1=divideMerge(lists, left, mid);
        ListNode*pHead2=divideMerge(lists, mid + 1, right);
        //加一个表头
        ListNode* head = new ListNode(0); 
        ListNode* cur = head;
        //两个链表都要不为空
        while(pHead1 && pHead2){ 
            //取较小值的节点
            if(pHead1->val <= pHead2->val){ 
                cur->next = pHead1;
                //只移动取值的指针
                pHead1 = pHead1->next; 
            }else{
                cur->next = pHead2;
                //只移动取值的指针
                pHead2 = pHead2->next; 
            }
            //指针后移
            cur = cur->next; 
        }
        //哪个链表还有剩,直接连在后面
        if(pHead1) 
            cur->next = pHead1;
        else
            cur->next = pHead2;
        //返回值去掉表头
        return head->next; 
    }
    
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        //k个链表归并排序
        if(lists.size()==0)
        return NULL;//样例有这种情况
        return divideMerge(lists, 0, lists.size() - 1);
    }
};

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

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

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

相关文章

  • 小白也能学会的链表 | C++ | 算法与数据结构 (新手村)

    本质:找到两个有序数据段中的第一个相同数据 解题:利用set的不重复性,首先把headA都塞到set中,再遍历headB找有没有已经出现在set中的节点即可。 注意! set的数据是ListNode* 不是 int。如果是int可能出现节点不同但是var相同的情况,而ListNode* 就不会。 时间复杂度:O(2n)

    2024年02月14日
    浏览(52)
  • 数据结构之链表练习与习题详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力,一起奔赴大厂。 目录 1.前言 2.习题解析 2.1习题一 2.2习题二 2.3习题三 2.4习题四 2.

    2024年02月05日
    浏览(43)
  • 合并 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)
  • 合并两个有序链表,将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    题记: 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 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)
  • 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 要将多个已按升序排

    2024年02月21日
    浏览(33)
  • 合并K个升序链表(LeetCode 23)

    给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 示例 1: 示例 2: 示例 3: Hard。 ★★★★☆ 我们可以想到一种最朴素的方法,依次将链表数组中的链表与最终结果合并。问题便退化成合并两个有序链表。 如何

    2024年01月19日
    浏览(35)
  • 23. 合并 K 个升序链表(递归分治)

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

    2024年01月16日
    浏览(31)
  • LeetCode 23 合并 K 个升序链表

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/merge-k-sorted-lists/description/ 博主Github :https://github.com/GDUT-Rp/LeetCode 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 示例1 : 示例2 : 示例3 : 提示: k == lists.length

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

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

    2024年02月12日
    浏览(31)
  • 【题解】合并两个排序的链表

    题目链接:合并两个排序的链表 解题思路1:迭代 创建一个新的单链表,对两个链表进行迭代,每次取较小元素放入新链表中,直至某一个链表为空,则结束循环,接着判断是否有某个链表没有遍历结束,再将未遍历结束的链表部分放入结果链表中。 一般创建单链表,都会设

    2024年02月15日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包