合并两个排序的链表

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

有两种方式：

一，遍历

/*
public class ListNode {
    int val;
    ListNode next = null;
 
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) 
    {
        if(list1==null)
            return list2;
        if(list2==null)
            return list1;
        if(list1==null&&list2==null)
       return null;
        ListNode a=list1;
        ListNode b=list2;
        ListNode temp=null; // 当作指针
        ListNode z=null;    // 缓存数组
        if(a.val<=b.val)
        {
            temp=a;
            a=a.next;
        }
        else
        {
            temp=b;
            b=b.next;
        }
        z=temp;
        while(a!=null&&b!=null)
        {
        if(a.val<=b.val)
        {
            temp.next=a;
            a=a.next;
            temp=temp.next;
        }
        else
        {
            temp.next=b;
            b=b.next;
            temp=temp.next;
        }
        }
        if(a==null)
        {
            temp.next=b;
        }
        else if(b==null)
        {
            temp.next=a;
        }
        return z;
        
    }
}

二，递归

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
     public ListNode Merge(ListNode list1, ListNode list2) {
         if(list1 == null){
             return list2;
         }else if(list2 == null){
             return list1;
         }
         ListNode list = null;
         if(list1.val <= list2.val){
             list = list1;
             list.next = Merge(list1.next,list2);
         }
         if(list2.val < list1.val){
             list = list2;
             list.next = Merge(list1,list2.next);
         }
         return list;
     }
}

还是对递归不太熟悉。

合并两个排序的链表

原文：http://zhenzhuangde.blog.51cto.com/10697385/1730696