合并两个排序的链表

1.题目
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
如，输入：{1,3,5},{2,4,6}；输出：{1,2,3,4,5,6}
2.思路：
方法一：迭代版本
牛客官方思路
初始化：定义cur指向新链表的头结点
操作：
如果l1指向的结点值小于等于l2指向的结点值，则将l1指向的结点值链接到cur的next指针，然后l1指向下一个结点值
否则，让l2指向下一个结点值
循环步骤1,2，直到l1或者l2为null
将l1或者l2剩下的部分链接到cur的后面
技巧：
一般创建单链表，都会设一个虚拟头结点，也叫哨兵，因为这样每一个结点都有一个前驱结点。
时间复杂度：O(m+n)，m,n分别为链表1、2的长度

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode cur=new ListNode(-1);//指向当前节点
        ListNode head=cur;//固定头节点位置
        while(list1!=null&&list2!=null){//直到有一个遍历完
            if(list1.val>list2.val){//如果1的值大于2的值
                cur.next=list2;//当前节点的下一个指定为list2
                list2=list2.next;//list2往后移动一位
            }else{//同上
                cur.next=list1;
                list1=list1.next;
            }
            cur=cur.next;//将当前节点后移
        }
        if(list1!=null){//如果list1比list2长，则将剩余的附在当前节点后
            cur.next=list1;
        }
        if(list2!=null){
            cur.next=list2;
        }
        return head.next;//返回头节点的下一位
    }
}

方法二：
递归版本
更新完当前结点后，令cur.next为再调用一次函数的值，注意传递参数的变化。在做链表题的时候，尤其注意保存我们最后返回的链表的头，以及是对下一个结点进行赋值，还是当当前指针移动到下一个结点。

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //============结束条件===============
        if(list1==null) return list2;//最后可能list2比list1长
        if(list2==null) return list1;//list1肯定比list2长
        //============递归体=================
        ListNode mergeHead=null;//当前节点
        if(list1.val<list2.val){
            mergeHead=list1;
            mergeHead.next=Merge(list1.next,list2);//递归
        }else{
            mergeHead=list2;
            mergeHead.next=Merge(list1,list2.next);
        }
        return mergeHead;
    }
}