解法一：迭代

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode cur = new ListNode(-1), head = cur;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return head.next;

    }
}

算法复杂度：

• 时间复杂度：O(M + N)
• 空间复杂度：O(1)

解法二：递归

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //递归的结束条件，如果l1和l2中有一个为空就返回
        if(l1==null || l2==null) {
            return (l1==null)? l2:l1;
        }
        //如果l1的值<=l2的值，就继续递归，比较l1.next的值和l2的值
        //l1.next和l2比较完后，会产生一个更小的节点x，将x加到当前l1的后面
        if (l1.val<=l2.val) {
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        //如果l1的值>l2的值，就继续递归，比较l1的值和l2.next的值
        } else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

算法复杂度：

• 时间复杂度：O(M + N)
• 空间复杂度：O(1)