《力扣每日一题》—— 合并两个有序链表

一时失言乱红尘 2024-04-23 15:37 70阅读 0赞

> ✅作者简介：大家好，我是小鱼儿，大家可以叫我鱼儿
> 
> ?博客首页：[是小鱼儿哈][Link 1]
> 
> ?系列专栏：[一起刷好题][Link 2]
> 
> ?每日一句**：努力不是重点，常态化才是关键。真正努力的人，能随时进入任何角色，在过程中找到感觉和快乐。**
> 
> ?博主也在学习阶段，如发现问题请告知，非常感谢?

> **原题链接**：[合并两个有序链表——力扣][Link 3]

![6299899046354c3eb8af5a218e255af9.png][]

## 迭代法 ##

一开始，没什么好的思路，只能老老实实的迭代

思路：

> **当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。**

**?一开始的代码**（里面有很多无用的代码）放在这就是让自己长长记性?

class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode dummyHead = new ListNode(0); // 定义一个虚拟头结点
            if (list1 == null) {
                return list2; // 处理链表为空的情况
            }
            if (list2 == null) {
                return list1;
            }
            if (list1.val < list2.val) {
                dummyHead.next = list1;
                list1 = list1.next;
            }
            else {
                dummyHead.next = list2;
                list2 = list2.next;
            }
            // 以上部分都是为了确定好新链表的真实头结点，
            // 但后来我才发现，完全没必要，直接用虚拟头结点操作就好，我写了很多无用的代码
            // 不能直接使用头结点，否则容易造成链表的丢失
            ListNode cur = dummyHead.next;
            while (list1 != null && list2 != null) { // 在两个链表不为空的情况下，按大小构建一个新的链表
                if (list1.val < list2.val) {
                    cur.next = list1;  // 因为list1此时比list2小，所有cur指向list1
                    cur = cur.next;     // 更新cur和list1, 注意list2不用更新
                    list1 = list1.next;
                }
                else {
                    cur.next = list2;
                    cur = cur.next;
                    list2 = list2.next;
                }
            }
            while (list1 != null) { // 当list2被合并完后，直接把剩下的list1添加到新的链表中
                cur.next = list1;
                cur = cur.next;
                list1 = list1.next;
            }
            while (list2 != null) { // 当list1被合并完后，直接把剩下的list2添加到新的链表中
                cur.next = list2;
                cur = cur.next;
                list2 = list2.next;
            }
            return dummyHead.next; // 返回新链表的头结点
        }
    }

**?优化后的代码**：

class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode dummyHead = new ListNode(0); // 定义一个虚拟头结点
            ListNode cur = dummyHead;
            while (list1 != null && list2 != null) { // 在两个链表不为空的情况下，按大小构建一个新的链表
                if (list1.val < list2.val) {
                    cur.next = list1;  // 因为list1此时比list2小，所以cur指向list1
                    cur = cur.next;     // 更新cur和list1, 注意list2不用更新
                    list1 = list1.next;
                }
                else {
                    cur.next = list2;
                    cur = cur.next;
                    list2 = list2.next;
                }
            }
            if (list1 != null) { // 当list2被合并完后，直接把剩下的list1添加到新的链表中
                cur.next = list1;
            }
            if (list2 != null) { // 当list1被合并完后，直接把剩下的list2添加到新的链表中
                cur.next = list2;
            }
            return dummyHead.next; // 返回新链表的头结点
        }
    }

**执行结果：**

![6fe597b91e2840c59f59179f81eadfc8.png][]

--------------------

## 递归写法 ##

对于递归我们考虑的无法就两个：

1.  **递归是怎样结束的？**
2.  **函数是如何进行递归操作的？**

?对于本题：

*  当两个链表中的**任意一个为空**时，递归就结束了。
 *  如何递归：我们判断 `l1` 和 `l2` 头结点哪个更小，然后较小结点的 **`next`** 指针指向**其余结点的合并结果。（调用递归）**

**如图所示：**

![62547194a10547cbba01de637d83fc56.png][]

![c536ca78ae384930859d594135aad525.png][]

![2f3b522bfa7141e5b3ebc45ed4a90895.png][]

![6510bf7365a344e7a74b6bc089f79b5a.png][]

![d973e80380384eb0b3215621375b930c.png][]

![c14a60c27378469ab17d38cbea629e47.png][]

![5a48acdd699f410ba72df88dd73ecb90.png][]

![7249a56576e94aafb6de76bf95d2aebc.png][]

**代码如下：**

>     class Solution {
>         public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
>             if (list1 == null) return list2; // 当list1此时为空，直接把剩下的List2接上
>             if (list2 == null) return list1; // 当list2此时为空，直接把剩下的List1接上
>             if (list1.val <= list2.val) {
>                 list1.next = mergeTwoLists(list1.next, list2); // 递归中的递
>                 return list1;  // 递归中的归
>             } 
>             else {
>                 list2.next = mergeTwoLists(list1, list2.next);
>                 return list2;
>             }
>         }
>     }

![6286edab88d84911ab5d6cb433191bca.png][]

[Link 1]: https://blog.csdn.net/weixin_61061381?type=blog
[Link 2]: https://blog.csdn.net/weixin_61061381/category_11776133.html
[Link 3]: https://leetcode-cn.com/problems/merge-two-sorted-lists/
[6299899046354c3eb8af5a218e255af9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/52f8e1fea5474f8bb38df715aa5d6ce1.png
[6fe597b91e2840c59f59179f81eadfc8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/99c36499c2b7490e80ec661ddb6f2e52.png
[62547194a10547cbba01de637d83fc56.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/6fbc877e93a24c639fca381f4ca0093e.png
[c536ca78ae384930859d594135aad525.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/4ed42da5bac2474ab46bd09ced1fd6ae.png
[2f3b522bfa7141e5b3ebc45ed4a90895.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/948a1b590b464e5091a1737668a8ff5a.png
[6510bf7365a344e7a74b6bc089f79b5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e0c049b7e10f4e7db02dec2daa88e483.png
[d973e80380384eb0b3215621375b930c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/2f0a129c748a4fa3b8c0d867a68b7512.png
[c14a60c27378469ab17d38cbea629e47.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/cb32c3104d3b453aa63e9ab1050c4336.png
[5a48acdd699f410ba72df88dd73ecb90.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e490a29e40b140d49ccfcc439f03eda4.png
[7249a56576e94aafb6de76bf95d2aebc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5506b89e55024923a3fed2a565b41871.png
[6286edab88d84911ab5d6cb433191bca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5c95f9e1dee949e6b9dc3efa7254418f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，70人围观）

还没有评论，来说两句吧...

相关阅读

相关《力扣每日一题》—— 合并两个有序数组

力扣链表题目——合并两个有序数组

本是古典何须时尚/ 2024年04月23日 15:38/ 0 赞/ 62 阅读

相关力扣每日一题（环形链表II）

力扣每日一题——环形链表II

深碍√TFBOYSˉ_/ 2024年04月23日 15:37/ 0 赞/ 64 阅读

相关《力扣每日一题》—— 合并两个有序链表

力扣刷题——合并两个有有序链表（两种方法来实现）

一时失言乱红尘/ 2024年04月23日 15:37/ 0 赞/ 71 阅读

相关力扣：21. 合并两个有序链表

[21. 合并两个有序链表 ][21. _] ![在这里插入图片描述][e6b3c944faac4c82a020df22f76ed5f5.png] /

- 日理万妓/ 2024年03月25日 14:08/ 0 赞/ 75 阅读

相关（每日一练C++）21. 合并两个有序链表

前言 C++是一种计算机高级程序设计语言，由C语言扩展升级而产生，最早于1979年由本贾尼·斯特劳斯特卢普在AT&T贝尔工作室研发。 C++既可以进行C语言的过程化

末蓝、/ 2023年10月04日 18:15/ 0 赞/ 35 阅读

相关合并两个有序链表21-力扣（链表-虚拟头结点-c）

题目描述 21.合并两个有序链表将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1： ![在这里插入图片描

谁践踏了优雅/ 2023年01月15日 02:14/ 0 赞/ 104 阅读

相关【每日一题】链表系列(2) —— 合并两个有序链表

> 写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我`热爱AI、热爱分享、热爱开源`！这博客是我对学习的一点总结与思考。如果您也对 `深度学习、机器视觉、算法、C

深藏阁楼爱情的钟/ 2022年11月30日 01:39/ 0 赞/ 138 阅读

相关力扣 21. 合并两个有序链表 JavaScript

代码如下 -------------------- //Definition for singly-linked list. function ListNo

短命女/ 2022年11月07日 14:50/ 0 赞/ 138 阅读

相关力扣合并两个有序数组

88. 合并两个有序数组给你两个按非递减顺序排列的整数数组 `nums1`和 `nums2`，另有两个整数 `m` 和 `n` ，分别表示 `nums1` 和 `n

「爱情、让人受尽委屈。」/ 2022年09月14日 00:18/ 0 赞/ 139 阅读

相关力扣-21题合并两个有序链表（C++）- 链表向后添加节点

题目链接：[https://leetcode-cn.com/problems/merge-two-sorted-lists/][https_leetcode-cn.com_pr

╰+攻爆jí腚メ/ 2022年08月30日 11:55/ 0 赞/ 133 阅读