JZ16：合并两个排序的链表

方法1：递归的方法：

如果表1当前值小于表2当前值，表1当前值成为新链表的表头，否则返回表2的当前值作为新链表的表头。
比较当前链表的值，较小的取其子链表继续递归。
当有一个链表取到子链表为空时，说明已经比较完成，可以直接返回非空的链表，返回值赋给了l1.next或者l2.next，但无论如何，最终还是沿着递归链不断返回，最终返回的是新有序链表的表头。

public ListNode MergeTwoList1(ListNode list1,ListNode list2){
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }

        ListNode newHead=null;
        if(list1.value>list2.value){
            newHead=list2;
            list2.next=MergeTwoList1(list1,list2.next);
        }
        else{
            newHead=list1;
            list1.next=MergeTwoList1(list1.next,list2);
        }
        return newHead;
    }

方法2：循环

新建一个链表cur，作为我们最终要输出的链表
如果表1当前值小于表2当前值cur.next = list1，否则cur.next = list2；
list1==null 说明list1遍历结束，剩下list2的节点的值肯定都是大于list1的所有节点
list2==null 说明list2遍历结束，剩下list1的节点的值肯定都是大于list2的所有节点

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode tmp = new ListNode(-1);
        ListNode cur = tmp;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            }
            else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if(l1 == null) cur.next = l2; 
        // l1遍历为空 那么l2还有节点呢，所以指向l2的节点。

        if(l2 == null) cur.next = l1; 
        // l2遍历为空 那么l1还有节点呢，所以指向l1的节点。

        return tmp.next;
    }