递归-21.合并两个有序链表-力扣(LeetCode)

白天的黑夜

发布于 2025-10-22 17:34:24

1210

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

个人主页

专栏：力扣刷题录_1白天的黑夜1的博客-CSDN博客、企鹅程序员：Linux 系统与网络编程_1白天的黑夜1的博客-CSDN博客

一、题目解析

1、合并两个有序链表

2、新链表节点是由给定两个链表拼接而成的

二、算法原理

解法：递归

如何写递归代码？

1、重复的子问题->函数头设计

2、只关心某一个子问题做什么->设计函数体

3、递归的出口

对于链表类的题，还是建议多画图，去体会链接的过程，题目链接放在下面，可以去动手敲敲

三、代码示例

四、递归展开图

看到最后，如果对您有所帮助，还请点赞、收藏和关注一键三连，在未来还会继续带来优秀的内容，感谢观看，我们下期再见！

一、题目解析

1、合并两个有序链表

2、新链表节点是由给定两个链表拼接而成的

二、算法原理

相信读者们在学习链表的时候，已经了解了通过循环实现链表的合并，本篇博客的目的是为了介绍用递归的思想来解决链表合并，下面开始进入正题。

解法：递归

还是和之前的一样，先分析合并的过程，看能不能从中找到子问题或者一些重复的行为

首先会注意到一点，我们合并的时候是有选择的，然后我们会把一个较小的节点作为下一个合并的节点。而且我们还注意到了并不是每次的节点都不为空，如果为空，则返回另一个节点；如果都为空则返回nullptr。

如何写递归代码？

1、重复的子问题->函数头设计

如何理解重复的子问题呢？我们在合并的时候选出了一个节点做头，那么我只需要把剩下的节点合并起来，返回合并后的头指针，我们直接更改指向就可以了，而剩下的节点也根据需求选出一个头节点，剩下的节点合并起来，由此发现了重复的子问题。递归函数f需要返回头指针，所以返回值类型为ListNode*，由于合并需要两个头指针，所以参数为两个待合并链表的指针。类似ListNode* f(l1,l2)，这是不是很像题目给的函数，所以题目给的函数头可以直接使用。

2、只关心某一个子问题做什么->设计函数体

就像我们上面分析的一样，需要对两个头指针存储的值进行比较，较小的那一个称为头节点(这里可以使用swap函数)；由于我相信递归函数可以帮我完成任务(即将剩余的节点链接起来，返回一个头指针)，所以再次调用递归函数传入做头结点的next和另一个头节点本身，我们只需将头节点的next指向递归函数的返回值即可。类似l1->next = f(l1->next,l2)。

3、递归的出口

当一个节点为空时，返回另一个非空节点；如果两个节点都为空，则返回nullptr。if else判断即可。

对于链表类的题，还是建议多画图，去体会链接的过程，题目链接放在下面，可以去动手敲敲

21. 合并两个有序链表 - 力扣（LeetCode）

三、代码示例

class Solution {
public:
    //递归
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
    {
        if(list1 == nullptr) return list2;
        if(list2 == nullptr) return list1;
        if(!list1&&!list2) return nullptr;
        if(list1->val >= list2->val) swap(list1,list2);
        list1->next = mergeTwoLists(list1->next,list2);
        return list1;
    }
};