合并两个有序链表 题目链接 21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1： 输入：l1 = [1,2,4
合并两个有序链表
题目链接 21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]示例 2：
输入：l1 = [], l2 = [] 输出：[]示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
题目解释
这应该是我们见识过多额一道题,之前我们都是使用迭代法来解决的.今天我们使用递归.我们发现,将两个两个有序链表合成一个链表,保证有序.
算法原理
对于递归解法,我们判断,这两个链表的data,此时拿到一个较小的链表节点,然后我们继续找剩下的链表的合并.
此时我们找到的重复的问题,就是简单的合并两个链表.
函数参数设置
然后把找到的节点的地址返回.那么此时的函数头和我们题目给的一样.
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2);
函数体设置
下面就是我们的函数体设计
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{
if(list1->val <= list2->val)
{
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
else
{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
编写代码
缺一个递归出口,如果
- 如果l1为空,那么返回l2
- 如果l2为空,那么返回l1
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1 == nullptr)
return list2;
if(nullptr == 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;
}
}
};
