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

题设类

//Definition for singly-linked list.
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

迭代法

这个在数据结构中学过，虽然那时候学的是 C语言，但是思想相同。
由于没有头节点，我们可以假设个头节点，更容易的返回合并后的链表。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //设置头节点
    ListNode head = new ListNode(-1);
    ListNode p = head;

    while(l1 != null && l2 != null){
        if(l1.val < l2.val){
            p.next = l1;
            l1 = l1.next;
        }else{
            p.next = l2;
            l2 = l2.next;
        }

        p = p.next;
    }

    //将两个链表中剩下的一个链表直接接在末尾
    p.next = (l1 == null)?l2:l1;

    return head.next;
}

时间复杂度 O(n+m)
空间复杂度 O(1)

递归法

我们可以递归的定义在两个链表的 merge 操作：

也就是说，头部比较小的一个与剩下元素的 merge 操作结果连接起来，就可以得到最终的链表

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //递归先考虑边界条件
    if (l1 == null) return l2;
    if (l2 == null)  return l1;

    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

时间复杂度 O(n+m)
空间复杂度 O(n+m)，由于需要n+m个栈帧