【题目】
将两个有序链表合并成一个有序链表
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4] Output: [1,1,2,3,4,4]
Example 2:
Input: l1 = [], l2 = [] Output: []
Example 3:
Input: l1 = [], l2 = [0] Output: [0]
【思路】
是把l1/l2的next指针向着对方或者自己的next相连
要想清楚为什么return L1/L2，他俩就能连一起，得到最终结果
if(l1.val<=l2.val){ l1.next= mergeTwoLists(l1.next,l2); return l1; } else{ l2.next= mergeTwoLists(l1,l2.next); return l2; }
L1<L2时，l1.next=l2， 连后主动权在l1，返回l1
L1>L2时，l2.next=l1， 连后主动权在l2，返回l2
============
虽然是个简单题但之前大晚上脑袋瓦特想歪了……错误思路也记下
L1<L2时，l1.next=l2， 返回l1
L1>L2时，l2.next=l2.next， 返回l2
看上去在分别处理，互不干扰死循环？？
醒醒，写成下面这样才叫互不干扰……上面其中一个指针动了，另一个没动，动了的指针就连到没动那了
l1.next= mergeTwoLists(l1.next,l2.next);
l2.next= mergeTwoLists(l1.next,l2.next);
【代码】
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1==null) return l2; if(l2==null) return l1; if(l1.val<=l2.val){ l1.next= mergeTwoLists(l1.next,l2); return l1; } else{ l2.next= mergeTwoLists(l1,l2.next); return l2; } } }
Q：为什么其中一个为null，就返回另一个？
A：因为是有序的，另一个剩余部分也是有序的，不用再遍历。
Q：为什么返回的另一个里就一定是结果？这里l1 l2代表的到底是什么，为什么是整串数而不是一部分
A：倒推，合并后的数列长度一定更长。那剩到最后返回的肯定是更长的。