21. [E] Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

递归，需要遍历两个链表的所有节点，因此复杂度 O(m+n) 。

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

循环，只需要遍历到最短的那一条链表，所以复杂度 O(min(m, n)) 。

class Solution {
    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (a != null && b != null) {
            if (a.val < b.val) {
                head.next = a;
                a = a.next;
            } else {
                head.next = b;
                b = b.next;
            }
            head = head.next;
        }
        if (a != null) {
            head.next = a;
        } else {
            head.next = b;
        }
        return dummy.next;
    }
}