算法修炼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