6._合并链表

• 2.10

  • 秒了？我是不是成了

• 1.24

  • 挑出排头兵，（排头兵的后面交给递归）返回排头兵。

• 1.19

  • 年纪大了就喜欢这种精巧递归题

递归

小的往后退,退到下一个递归子问题、

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

list1: 1 → 2 → 4
list2: 1 → 3 → 4
递归展开：
merge(1→2→4, 1→3→4)
   → 1.next = merge(2→4, 1→3→4)
       → 1.next = merge(2→4, 3→4)
           → 2.next = merge(4, 3→4)
               → 3.next = merge(4, 4)
                   → 4.next = merge(null, 4)
                       → return 4