【剑指offer】合并两个排序的链表

题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
1、思路分析
解法一：非递归
新建两个结点，一个用来保留头结点，一个用来移动扩充新结点。看了别人的思路后，有两点需进行优化：如果我们每次更新的是cur.next，更新完后令cur=cur.next，我们就不需要提前对head进行赋值，可以简化很多代码，也使思路更加清晰，正是cur=cur.next使得head和cur的值不再关联。而是循环时，注意条件是两个链表不同时为空，而不是任意一个链表不为空，这样可以减少很多循环的次数，循环结束后再判断是哪一个链表为空。
解法二：递归
更新完当前结点后，令cur.next为再调用一次函数的值，注意传递参数的变化。在做链表题的时候，尤其注意保存我们最后返回的链表的头，以及是对下一个结点进行赋值，还是当当前指针移动到下一个结点。
2、代码

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null){
            return list2;
        }else if(list2==null){
            return list1;
        }
        ListNode pMergeHead = null;
        if(list1.val<list2.val){
            pMergeHead = list1;
            pMergeHead.next = Merge(list1.next,list2);
        }else{
            pMergeHead = list2;
            pMergeHead.next = Merge(list1,list2.next);
        }
        return pMergeHead;
    }
}