原题链接：合并两个有序链表——力扣
迭代法
一开始，没什么好的思路，只能老老实实的迭代
思路：
当 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; // 返回新链表的头结点 } }
执行结果：
递归写法
对于递归我们考虑的无法就两个：
- 1.递归是怎样结束的？
- 2.函数是如何进行递归操作的？
📝对于本题：
- 当两个链表中的任意一个为空时，递归就结束了。
- 如何递归：我们判断
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; } } }
