【Hot100】21. 合并两个有序链表

21. 合并两个有序链表
简单题
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

递归
发现有意思的一个图哈哈哈哈哈

• 终止条件：当两个链表都为空时
• 如何递归：我们判断list1 和 list2 的头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。（调用递归）
• 如果 list1 的 val 值更小，则将 list1 .next 与排序好的链表头相接，list2同理
• 返回值：每一层调用都返回排序好的链表头

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

    }
}

• 迭代

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