面试题25(剑指offer)--合并两个排序的链表

题目：

输入两个递增序列链表，合并这两个链表并使新链表中的结点仍然是递增排序的。

思路：

从头开始比较两个递增的链表，较小的节点比如list1先进入新链表，然后list1.next与list2继续比较，直至两个链表合并完成。

代码：

    public static ListNode merge(ListNode list1,ListNode list2){
        if (list1==null){
            return list2;
        }else if (list2==null){
            return list1;
        }
        ListNode newNode = null;
        if (list1.val<list2.val){
            newNode = list1;//值小的节点先进新链表
            newNode.next=merge(list1.next,list2);
        }else{
            newNode = list2;
            newNode.next=merge(list1,list2.next);
        }
        return newNode;
    }