天津网站建设找哪家,产品线上推广方式,好看的网站源码,腾讯广告代理商✨博主#xff1a;命运之光 #x1f984;专栏#xff1a;算法修炼之练气篇#xff08;C\C版#xff09; #x1f353;专栏#xff1a;算法修炼之筑基篇#xff08;C\C版#xff09; #x1f433;专栏#xff1a;算法修炼之练气篇#xff08;Python版#xff09; … ✨博主命运之光 专栏算法修炼之练气篇C\C版 专栏算法修炼之筑基篇C\C版 专栏算法修炼之练气篇Python版 ✨博主的其他文章点击进入博主的主页 前言欢迎来到这个LeetCode每日算法题专栏 无论你是编程新手还是有一定经验的开发者掌握算法和数据结构都是成功的关键。在这个专栏里我将每天为你分享一道算法题并提供简单易懂的解析和讲解。 ☀️通过每日挑战你将逐渐培养解决问题的思维方式掌握重要的编程技巧。无论是面试准备还是日常编码这些知识都将对你大有裨益。 让我们一起开始这段充满乐趣和成长的学习之旅吧希望你能从中受益开拓编程的新视野 目录
21. 合并两个有序链表
正确答案
方法一暴力破解
提交记录
详细解析该题代码方法一暴力破解
方法二递归法解题
提交记录
详细解析该题代码方法二递归法解题
结语 21. 合并两个有序链表 正确答案
方法一暴力破解
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode dummyListNode(-1);ListNode *prevdummy;while(l1 ! nullptr l2 ! nullptr){if(l1-val l2-val){prev-nextl1;l1 l1-next;}else{prev-next l2;l2 l2-next;}prev prev-next;}prev-nextl1nullptr?l2:l1;return dummy.next;}
};
提交记录 详细解析该题代码方法一暴力破解
这段代码是一个用于合并两个升序链表的C函数其中使用了单链表的数据结构。现在我将逐行解析代码的功能
定义了一个单链表的数据结构 ListNode每个节点包含一个整数值 val 和一个指向下一个节点的指针 next。该数据结构提供了三个构造函数 ListNode()无参构造函数初始化 val 为0next 为nullptr。ListNode(int x)带参构造函数初始化 val 为给定的整数xnext 为nullptr。ListNode(int x, ListNode *next)带参构造函数初始化 val 为给定的整数xnext 为指向给定节点的指针。
接下来是一个C类 Solution 的定义。该类中有一个公共成员函数 mergeTwoLists它用于合并两个升序链表。该函数接受两个指向链表头节点的指针 l1 和 l2并返回一个指向合并后链表头节点的指针。在 mergeTwoLists 函数中 创建了一个名为 dummy 的 ListNode 对象并初始化其值为-1。这个 dummy 节点在合并过程中起到了哨兵节点的作用它不包含实际数据只是用来简化代码逻辑。创建一个指向 dummy 节点的指针 prev用于跟踪合并后链表的末尾节点。
使用 while 循环进行链表的合并循环条件是 l1 和 l2 都不为nullptr即还有节点需要合并。 在循环体中比较 l1-val 和 l2-val 的大小如果 l1 的值小于 l2则将 l1 添加到合并后链表的末尾并将 l1 指针移动到下一个节点否则将 l2 添加到合并后链表的末尾并将 l2 指针移动到下一个节点。然后将 prev 指针移动到合并后链表的末尾。
当循环结束后有可能 l1 或 l2 中还有剩余节点未合并此时需要将剩余的部分直接添加到合并后链表的末尾。这里使用了三目运算符 l1nullptr?l2:l1 来确定应该将哪个链表的剩余部分添加到末尾。最后返回 dummy.next即合并后链表的头节点的指针。由于 dummy 是一个临时节点实际的合并后链表从 dummy.next 开始。
总体来说这段代码通过迭代遍历两个升序链表根据节点值的大小将节点逐个合并并返回合并后的链表头节点的指针。合并后的链表仍然保持升序。
方法二递归法解题
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 nullptr) {return l2;}if (l2 nullptr) {return l1;}if (l1-val l2-val) {l1-next mergeTwoLists(l1-next, l2);return l1;} else {l2-next mergeTwoLists(l1, l2-next);return l2;}}
};
提交记录 详细解析该题代码方法二递归法解题
除了迭代法外还有递归法可以解决合并两个升序链表的问题。我将为你介绍递归法的解题思路和代码示例。
递归法的思路是基于合并两个升序链表的子问题。假设我们已经知道如何合并两个以 l1 和 l2 为头节点的升序链表我们可以将问题转化为合并以 l1-next 和 l2 为头节点的升序链表并将结果连接到 l1 上。这样问题规模不断缩小最终合并两个链表的问题将转化为合并两个小一些的链表的问题直到其中一个链表为空。
下面是用递归法解决问题的代码示例
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 nullptr) {return l2;}if (l2 nullptr) {return l1;}if (l1-val l2-val) {l1-next mergeTwoLists(l1-next, l2);return l1;} else {l2-next mergeTwoLists(l1, l2-next);return l2;}}
};
在递归函数 mergeTwoLists 中我们首先处理边界情况即如果其中一个链表为空直接返回另一个链表。然后我们比较 l1-val 和 l2-val 的大小如果 l1 的值小于 l2则将 l1 的下一个节点与合并后的链表连接并返回 l1否则将 l2 的下一个节点与合并后的链表连接并返回 l2。
递归法的思路较为简洁但需要注意对递归深度的控制防止出现栈溢出的情况。在实际应用中可能需要对递归深度进行限制或使用迭代法来处理大规模的链表。
结语 再接再厉继续加油 本章的内容就到这里了觉得对你有帮助的话就支持一下博主把~
点击下方个人名片交流会更方便哦~ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
