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 dummy=ListNode(-1);
ListNode *prev=&dummy;
while(l1 != nullptr && l2 != nullptr){
if(l1->val < l2->val){
prev->next=l1;
l1 = l1->next;
}
else{
prev->next = l2;
l2 = l2->next;
}
prev = prev->next;
}
prev->next=l1==nullptr?l2:l1;
return dummy.next;
}
};
这段代码是一个用于合并两个升序链表的C++函数,其中使用了单链表的数据结构。现在,我将逐行解析代码的功能:
总体来说,这段代码通过迭代遍历两个升序链表,根据节点值的大小将节点逐个合并,并返回合并后的链表头节点的指针。合并后的链表仍然保持升序。
/**
* 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。
递归法的思路较为简洁,但需要注意对递归深度的控制,防止出现栈溢出的情况。在实际应用中,可能需要对递归深度进行限制或使用迭代法来处理大规模的链表。
再接再厉,继续加油!
本章的内容就到这里了,觉得对你有帮助的话就支持一下博主把~