一起刷好题|《力扣每日一题》—— 合并两个有序链表 leetcode|java|链表

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

原题链接：合并两个有序链表——力扣

文章图片

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

当 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; // 返回新链表的头结点 } }

执行结果：

文章图片

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

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

对于本题：

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

如图所示：

文章图片

文章图片

【一起刷好题|《力扣每日一题》—— 合并两个有序链表】

文章图片

文章图片

代码如下：

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; } } }