21. Merge Two Sorted Lists

题设

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

要点

• 链表归并

可以用递归来做。如果h1==null返回h2;如果h2==null返回h1；
否则，维护一个root，一个header=root,h1=l1,h2=l2。然后进行递归;
每次让header指向h1，h2中val较小的节点(如h1)，同时让header=header.next,h1=h1.next。
直到h1或h2为空。如果h1为空，则header=h2，否则相反，把剩下的节点都接上即可。

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null && l2 == null)
            return null;
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;
        
        ListNode root = new ListNode(0);
        ListNode header = root;
        ListNode h1 = l1;
        ListNode h2 = l2;
        merge(header , l1 , l2);
        return root.next;
    }
    
    public void merge(ListNode header , ListNode h1, ListNode h2){
        if(h1 == null){
            header.next = h2;
            return;
        }
        if(h2 == null){
            header.next = h1;
            return;
        }
        
        if(h1.val < h2.val){
            header.next = h1;
            header = header.next;
            merge(header , h1.next , h2);
        }
        else{
            header.next = h2;
            header = header.next;
            merge(header , h1 , h2.next);
        }
    }