【剑指Offer】16、合并两个排序的链表

题目描述：

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

解题思路：

首先需要判断几个特殊情况，即判断输入的两个指针是否为空。如果第一个链表为空，则直接返回第二个链表；如果第二个链表为空，则直接返回第一个链表。如果两个链表都是空链表，合并的结果是得到一个空链表。

两个链表都是排序好的，我们只需要从头遍历链表，判断当前指针，哪个链表中的值小，即赋给合并链表指针，剩余的结点仍然是排序的，所以合并的步骤和之前是一样的，所以这是典型的递归过程，用递归可以轻松实现。

举例：

编程实现（Java）：

    //方法一：递归实现
    public ListNode Merge(ListNode list1,ListNode list2) {
   	if(list1==null)
            return list2;
        if(list2==null)
            return list1;
        ListNode head=null;    //头节点
        if(list1.val<=list2.val){
            head=list1;
            head.next=Merge(list1.next,list2);
        }else{
            head=list2;
            head.next=Merge(list1,list2.next);
        }
        return head;
    }

    //方法二：非递归实现
    public ListNode Merge(ListNode list1,ListNode list2) {
    	if(list1==null)
            return list2;
        if(list2==null)
            return list1;
        ListNode head=new ListNode(-1);//头节点
        ListNode thehead=head;
        while(list1!=null && list2!=null){
            if(list1.val<=list2.val){
                thehead.next=list1;
                list1=list1.next;
            }else{
                thehead.next=list2;
                list2=list2.next;
            }
            thehead=thehead.next;
        }
        if(list1!=null)  //归并完需要检查哪个链表还有剩余
            thehead.next=list1;
        if(list2!=null)
            thehead.next=list2;
        return head.next;
    }