方法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:循环

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;
    }