21.合并两个有序链表
生活真的是不容易啊，我感觉刷题就是正视智商的过程。它视我为渣渣，我视它为大腿。必须练！必须坚持！爬坡哪有不辛苦的啊~
虽然这个力扣上面的这个题目标注的是简单，simple,可是我觉得在递归上面是一点也不简单，哼！（我好笨，呜呜呜~）
方法一：暴力解法（迭代法）
题解：用一个辅助结点。然后比较两链表此时的结点值。看代码吧
代码如下：
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//1.迭代法。用一个指针来维护和判断，并进行连接。amazing!
ListNode prehead=new ListNode(-1);
ListNode prev=prehead;
while(list1!=null&&list2!=null){
if(list1.val<=list2.val){
prev.next=list1;
list1=list1.next;
}else{
prev.next=list2;
list2=list2.next;
}
prev=prev.next;
}
prev.next=list1==null?list2:list1;
return prehead.next;
}
}方法二：递归
我知道你可能觉得很简单，可对于一个差不多是小白的而言，搞懂这个原理是折磨，是欲哭无泪，是心酸...
首先，我的问题就在于没搞懂它所返回的值，让我有点懵。你要知道，递归完之后，是要回溯的！且必须！。所以在递归完之后，根据其返回的结果对其进行一个整理，最后进行返回即可。
那返回的结果给到哪呢，给到函数mergeTwoLists(x,x)呀，家人，然后再执行。
这里说一下代码执行的这个流程，说完之后再想想估计你就明白了。
- 首先先判断两条链表是否为空，也要判断在其递归的过程中是否走到了尽头。因为这l1和l2两个指针是在不断移动的。
- 若不为空，则比较此时两条链表中元素值的大小，因为是根据这个在往下递归。继续调用自己的函数,并重复直到两天链表中有一条为空。
- 然后将返回的值给l1.next或者l2.next，并将此时的l1或者l2返回给上一级的1.next或者l2.next实现一个链表的重组，直到回溯结束为止。我这里有个图片，你可以看看，就是有点潦草。
代码如下：
/**
* Definition for singly-linked list.
* 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; }
* }
*/
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;
}
}
}祝你刷题快乐~
