LeetCode21题-合并有序链表
零 题解
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.
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一 思路分析
1 通过递归实现
先找到基准条件：如果l1==null，直接返回l2即可，反之，如果l2=null，则直接返回l1；
向解决问题正确方向缩小问题规模：
如果l1的第一个节点值l1.val<=l2.val；则考虑将除l1的第一个点之外的链表l1.next，和l2一起，继续合并成有序链表。令合并之后的链表头节点为retNode；然后将l1.next指向retNode，最后返回l1即可；
如果l1的第一个节点值l1.val>l2.val；则考虑将l1和除l2的第一个节点之外的链表l2.hext一起，继续合并成有序链表。令合并之后的链表头节点为retNode；然后将l2.next指向retNode,最后返回l2即可。
2 通过迭代处理
引入虚拟头节点dummyHead=new ListNode(-1)，令其指向一个不存在于结果中的节点。
然后比较l1和l2的第一个节点值，如果l1.val<=l2.val，则dummyHead.next=l1，且l1的指针继续后移一位，l2的指针保持不变，再继续比较l1.val和l2.val。哪个链表的当前节点值比较小，则让虚拟头节点指向该链表的当前节点，且当前节点值小的链表指针继续后移，另外一个链表指针保持不变。一直持续这个过程，直到其中某一个链表为空了。
接下来，再判断哪个链表为空，再将另外一个不为空的链表的余下所有元素都拼接到dummyHead.next上。
最后，返回dummyHead.next即可。当然，这里不能直接这样用，因为虚拟头节点已经移动到结果集上的某个位置上了。我们需要提前将这个虚拟头节点给“留存保护”起来，最后再返回它的next即可。
二 代码实现
1 递归代码
/**
* 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;
}else if(l2==null){
return l1;
}else if(l1.val<=l2.val){
ListNode retNode=mergeTwoLists(l1.next,l2);
l1.next=retNode;
return l1;
}else{
//这种写法跟上述的写法本质一样，省去了一个临时变量retNode
l2.next=mergetTwoLists(l1,l2.next);
return l2;
}
}
}2 非递归实现
/**
* 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){
//开启一个虚拟头节点，其val为任意值，反正它不会被引用到，其next=null;
ListNode dummyHead = new ListNode(-1,null);
//开启另外一个临时变量，用于"追踪记录"这个虚拟头节点的位置
ListNode retNode = dummyHead;
//开始递归判断l1和l2，当他们都不为空时，让虚拟头节点和当前值小的那个节点的指针不停向后移动
while( l1 != null && l2 != null){
//l1的当前值比较小时，让虚拟头节点.next指向l1,同时，l1也向后移动一个位置，此时l2保持不变
if(l1.val<=l2.val){
dummyHead.next=l1;
l1=l1.next;
dummyHead=dummyHead.next;
}else{
dummyHead.next=l2;
l2=l2.next;
dummyHead=dummyHead.next;
}
}
//如果l1已经遍历结束，其为空，则将l2余下所有元素继续拼接到dummyHead.next
if(l1==null) dummyHead.next=l2;
if(l2==null) dummyHead.next=l1;
return retNode.next;
}
}三 小结
我现在用递归思想来处理程序写代码，犹如在小学二、三年级时，造句写作文练习时，偶尔用到一个四字成语，作文结尾时呼应题目的那一句话。嗨，递归真的是个好东西，犹如神来之笔。
