【Hot100】21. Merge two ordered linked lists

21. Merge two ordered lists
Simple questions
Merge two ascending linked lists into a new Ascending Link list and return . The new linked list is made up of all the nodes of the given two linked lists .

recursive
Find an interesting picture hahahaha

• Termination conditions ： When both linked lists are empty
• How to recurse ： We can judge list1 and list2 Which is smaller , Then the smaller nodes next The pointer points to the merge results of other nodes .（ Call recursion ）
• If list1 Of val Less valuable , Will list1 .next Connect with the sorted chain header ,list2 Empathy
• Return value ： Each layer call returns the sorted chain header

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    
        if (list1 == null) {
    
            return list2;
        }
        else if (list2 == null) {
    
            return list1;
        }
        else if (list1.val < list2.val) {
    
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
        else {
    
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }

    }
}

• iteration

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
    ListNode dummyHead = new ListNode(0);
    ListNode tail = dummyHead;
    while (l1 != null && l2 != null) {
    
        if (l1.val < l2.val) {
    
            tail.next = l1;
            l1 = l1.next;
        } else {
    
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }

    tail.next = l1 == null? l2: l1;

    return dummyHead.next;
}