合并两个链表

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

思路：
使用类似于归并排序的算法，分别有两个指针指向list1和list2的结点，合并的lisHead指向其中较小的一个结点。当其中一个结点全部比较结束时（null），可以将合并的结点的next指向另一个未结束的链表的结点。

代码实现：

/**
     * 非递归版：类似于归并排序
     * @param list1
     * @param list2
     * @return
     */
    public ListNode merge(ListNode list1,ListNode list2){
        if(list1 ==null && list2 ==null)
            return null;
        if(list1 ==null)
            return list2;
        if(list2 ==null)
            return list1;
        ListNode head = null;
        //首先给头结点赋值
        if(list1.val < list2.val){
            head = list1;
            list1 = list1.next;

        }else {
            head = list2;
            list2 = list2.next;
        }
        ListNode current = head;
        //归并，选择其中小的结点作为next，之后list1（list2）、current均后移一位
        while ( list1 !=null && list2!=null){
            if(list1.val <= list2.val){
                current.next = list1;
                list1 = list1.next;
            }else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;

        }
        //将后面的结点补上即可
        if (list1!=null)
            current.next = list1;
        if (list2!=null)
            current.next = list2;
        return head;

    }