21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
} else if (list2 == null) {
return list1;
} else if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}
终止条件：当两个链表都为空时，表示我们对链表已合并完成。
如何递归：我们判断 list 1 和 list 2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。（调用递归）
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode head = new ListNode();
ListNode last = head;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
last.next = list1;
list1 = list1.next;
} else {
last.next = list2;
list2 = list2.next;
}
last = last.next;
}
if (list1 != null)last.next = list1;
if (list2 != null) last.next = list2;
return head.next;
}
}
捋一捋题意： 1. 给你两个有序链表 2. 合并为一个有序链表
可以简单理解为： 同时遍历两个链表， 当前遍历的结点，谁的结点小，就把谁的结点”摘下来”，”安装”在新链表上就可以了吧。
这里为了简单方便的处理， 给新链表先”安装”一个头结点，然后比如例一：
将 l2 链表的 1 结点摘下来，放到新链表的尾部。
将 l1 链表的 1 结点摘下来，放到新链表的尾部。
将 l1 链表的 2 结点摘下来，放到新链表的尾部。 同理…
最后l2 链表被摘完了， l2 == null ，l1 链表剩下的部分，”安装”在新链表的尾部。
Original: https://blog.csdn.net/starry_night_summer/article/details/127816944
Author: 余忆北
Title: leetcode 21
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/654672/
转载文章受原作者版权保护。转载请注明原作者出处！