题目：
将两个升序链表合并为一个新的
升序
链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
1、# 自定义链表类；
重写toString方法，便于观察链表数据（可有可无）；
/**
自定义链表类
*/
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
@Override
public String toString() {
StringBuilder sb=new StringBuilder();
ListNode next=null;
sb.append("[");
sb.append(val);
next=this.next;
while (next !=null){
sb.append(",");
sb.append(next.val);
next=next.next;
}
sb.append("]");
return sb.toString();
}
}
2、# 实现方法
public class Solution21 {
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//l1链表为空，则输出l2，否则输出l1
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
//如果l1,l2不为空，则比较首节点值的大小，如果l1小则l1.next->（mergeTwoLists(l1.next,l2)）
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
//反之则l2.next->（mergeTwoLists(l1,l2.next)）
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
public static void main(String[] args) {
ListNode l1=new ListNode(1);
ListNode nextNode1=new ListNode(2);
ListNode nextNode2=new ListNode(3);
l1.next=nextNode1;
nextNode1.next=nextNode2;
ListNode l2=new ListNode(1);
ListNode nextNode3=new ListNode(3);
ListNode nextNode4=new ListNode(4);
l2.next=nextNode3;
nextNode3.next=nextNode4;
System.out.println(mergeTwoLists(l1,l2));
}
}
3、#图解
[1,2,3] [1,3,4]
1<1 false
[1,2,3] [3,4] 第1次递归 l2.next = mergeTwoLists(l1, l2.next);
1<3 true
[2,3] [3,4] 第2次递归 l1.next = mergeTwoLists(l1.next, l2);
2<3 true
[3] [3,4] 第3次递归 l1.next = mergeTwoLists(l1.next, l2);
3<3 false
[3] [4] 第4次递归 l2.next = mergeTwoLists(l1, l2.next);
3<4 true
null [4] 第5次递归 l1.next = mergeTwoLists(l1.next, l2);
l1=null return l2 程序结束
return [4] 返回 4
return l1 [3,4] 返回第5次递归结果
return l2 [3,3,4] 返回第4次递归结果
return l1 [2,3,3,4] 返回第3次递归结果
retruen l1 [1,2,3,3,4] 返回第2次递归结果
return l2 [1,1,2,3,3,4] 返回第1次递归结果