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

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

本期给大家带来的是 合并两个排序的链表 这道题的讲解!!!

 接下来,我们还是先从题干的内容入手,先分析一波题目,在进行画图思考操作。

💨 题目如下:

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

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

示例1

输入:{1,3,5},{2,4,6}

返回值:{1,2,3,4,5,6}

示例2

输入:{},{}

返回值:{}

示例3

输入:{-1,2,4},{1,3,4}

返回值:{-1,1,2,3,4,4}


解题思想

a)迭代思想

b)递归思想


💥题意分析:

我们读完题意后,发现题干的意思其实很简单。

  1. 给出的链表均为有序的链表,因此免除了我们自己对其进行排序的操作;
  2. 其次,对于链表中的元素如果有重复项,那么排序后输出的只有一项即可;

接下来,我给出两种不同的思想来进行解决!


a)迭代思想

💨 解题思路:

  1. 首先整体的思路即是 :从首结点开始依次比较两个链表中的结点的值,比较完一次之后把小的结点插入到新的链表上,紧接着往后移动一个位置在进行比较,依次类推。
  2. 如果比较过程中遇到相同的结点,随便插入一个即可
  3. 最后,当比较过程中如果有一方的链表为空了,则只需将另外一个链表剩余的结点值链接到链表的结尾即可。

图解如下:

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

  •  第一步:

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

 文章来源地址https://www.toymoban.com/news/detail-411908.html

  •  第二步:

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

 

  •  第三步:

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

 

  •  第四步:

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

  •  第五步:

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

  •  第六步:

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

 

 

代码如下:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/

class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
		//首先,判断一下刚开始时是否有链表为空的情况
        if (pHead1 == NULL) return pHead2;
        if (pHead2 == NULL) return pHead1;
        if (pHead1 == NULL && pHead2 == NULL) 
		{
            return NULL;
        }
		
        //我们在进行初始化操作时,可以设置一个虚拟头结点,也叫哨兵结点
		//这样做的好处是便于,刚开始时每一个插入的结点都有一个前驱结点
		ListNode* head=new ListNode(-1); 
		ListNode *newhead=head;

		 //接下来就开始进行进行比较
		 while(pHead1 && pHead2)
		 {
			 if(pHead1->val <= pHead2->val) //比较得出结点值中较小的一个
			 {
				newhead->next=pHead1; //取出较小的一个节点
                pHead1=pHead1->next;  //取出后往后移动一位
			 }
			 else 
			 {
				newhead->next=pHead2;
                pHead2=pHead2->next;		 
			 }
			 newhead=newhead->next; //链接一位后,就将新链表的指向往后移一位

		 }
        //比较完之后如果其中一个为空了,则将另外一个链表的结点链接在后面
		if(pHead2==NULL) 
            newhead->next=pHead1;
        if(pHead1==NULL)
            newhead->next=pHead2;
        return head->next;
    }
};

💨 性能分析:

  • 时间复杂度:因为需要遍历两个链表,所以时间复杂度为O(n+m)  n m 分别表示pHead1, pHead2的长度
  • 空间复杂度 :  因为没开辟新空间。所以空间复杂度为O(1)

b)递归思想

💨 解题思路:

  • 对于 【 ListNode* Merge(ListNode* pHead1, ListNode* pHead2) 】这一段代码的函数功能为:合并两个单链表,返回两个单链表头结点值小的那个节点。
  • 因此,本题递归的思想即为:两个链表头部值较小的一个节点与剩下元素的 【Merge】操作结果合并

代码如下:

class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //首先,还是先判断一下刚开始时是否有链表为空的情况
        if (pHead1 == NULL) return pHead2;
        if (pHead2 == NULL) return pHead1;
        if (pHead1 == NULL && pHead2 == NULL) {
            return NULL;
        }

         //如果一个链表的首结点比另外一个链表的首结点大,此时递归去查看较小链表中其余结点的值跟此时较大链表的首结点值的大小
        if (pHead1->val <= pHead2->val) 
		{
            pHead1->next = Merge(pHead1->next, pHead2);
            return pHead1;
        } 
		else //同理
		 {
            pHead2->next = Merge(pHead1, pHead2->next);
            return pHead2;
        }
    }
};

 

💨 性能分析:

  • 时间复杂度:因为需要遍历两个链表,所以时间复杂度为O(n+m)  n m 分别表示pHead1, pHead2的长度
  • 空间复杂度 : 递归调用 merge 函数时需要消耗栈空间,栈空间的大小取决于递归调用的深度。结束递归调用时 merge  函数最多调用 n+m ,所以空间复杂度为O(n+m)

到此关于本题便讲解结束了,当然本题的结题思路并不止这两种,如果大家有兴趣还可以研究研究!!!

 

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

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

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

相关文章

  • 【C/C++练习】合并k个已排序的链表

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

    2024年02月09日
    浏览(38)
  • 【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日
    浏览(46)
  • 合并 k 个升序的链表

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

    2024年02月10日
    浏览(48)
  • 剑指 Offer 09. 用两个栈实现队列

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸剑指 Offer  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸

    2024年02月08日
    浏览(32)
  • 剑指offer刷题笔记-链表

    少年何妨梦摘星 敢挽桑弓射玉衡 解决与链表相关的问题总是有大量的指针操作,而指针操作的代码总是容易出错的。很多面试官喜欢出与链表相关的问题,就是想通过指针操作来考察应聘者的编码功底。 题目链接 来自于 AcWing 、 Leetcode (LCR) 目录  从尾到头打印链表 题目

    2024年02月21日
    浏览(35)
  • 剑指 Offer 24. 反转链表

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸剑指 Offer  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸

    2024年02月06日
    浏览(41)
  • LeetCode 剑指offer 09.用两个栈实现队列

    用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) 这道题很简单,主要理解栈与队列的区别,注意细节就可以 c++ Go

    2024年02月09日
    浏览(34)
  • 剑指 Offer 06. 从尾到头打印链表

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸剑指 Offer   📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸君一同

    2024年02月08日
    浏览(42)
  • (链表) 剑指 Offer 24. 反转链表 ——【Leetcode每日一题】

    难度:简单 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: 输入 : 1-2-3-4-5-NULL 输出 : 5-4-3-2-1-NULL 限制 : 0 = 节点个数 = 5000 注意:本题与 206. 反转链表 相同。 💡思路: 法一:递归 可以将本问题分解成子问题: 1 - (剩余部分的反转)

    2024年02月15日
    浏览(47)
  • 【栈和队列】剑指 Offer 09. 用两个栈实现队列

    用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) 示例 1: 输入: [“CQueue”,“appendTail”,“deleteHead”,“deleteHead”,“deleteHead”] [[]

    2024年02月01日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包