合并两个有序链表.md

题目

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

我的思路

1. 以一个链表为基础，插空法，将另一个链表每一个结点与基础链表的空格两边结点进行比较，大于左边小于右边即插空。复杂度O(n*(n-1))。 xxxxxxxxxxxx

2. 首先直接合并两个链表，然后重新排序。（链表的二分法？从中间开始，两两比大小，互换位置）xxxxxxxxxxxxx

高票方案

链接：https://www.nowcoder.com/questionTerminal/d8b6b4358f774294a89de2a6ac4d9337 来源：牛客网

递归版本：

public ListNode Merge(ListNode list1,ListNode list2) {
       if(list1 == null){
           return list2;
       }
       if(list2 == null){
           return list1;
       }
       if(list1.val <= list2.val){
           list1.next = Merge(list1.next, list2);
           return list1;
       }else{
           list2.next = Merge(list1, list2.next);
           return list2;
       }        
   }

非递归：

链接：https://www.nowcoder.com/questionTerminal/d8b6b4358f774294a89de2a6ac4d9337
来源：牛客网

if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode mergeHead = null;
        ListNode current = null;      
        while(list1!=null && list2!=null){
            if(list1.val <= list2.val){
                if(mergeHead == null){
                   mergeHead = current = list1;
                }else{
                   current.next = list1;
                   current = current.next;
                }
                list1 = list1.next;
            }else{
                if(mergeHead == null){
                   mergeHead = current = list2;
                }else{
                   current.next = list2;
                   current = current.next;
                }
                list2 = list2.next;
            }
        }
        if(list1 == null){
            current.next = list2;
        }else{
            current.next = list1;
        }
        return mergeHead;