将两个升序链表合并为一个新的升序链表

要求

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

示例

示例 1：

1 2	输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

示例 2：

1 2	输入：l1 = [], l2 = [] 输出：[]

示例 3：

1 2	输入：l1 = [], l2 = [0] 输出：[0]

思路

ListNode 的定义

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

1、递归

看到一个大佬的图解思路，感觉非常清晰：一看就会，一写就废？详解递归

图解

首先确定头节点。L1 和 L2 第一个节点值都是 1，比较完大小后，第一次递归结束，以 L2 第一个节点作为头节点，则 L2.next 指向剩下需要递归的部分（list1, list2.next）
同理，第二次递归会得到一个较小的值，此时这个值指向剩下需要递归的部分，而 L2 第一个节点则指向第二次递归时得到的较小的值
一直递归下去，直到指向了 null，递归结束，返回最后剩下的部分

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

复杂度分析

时间复杂度：O(n + m)，其中 n 和 m 分别为两个链表的长度。

空间复杂度：O(n + m)

2、迭代

首先，我们设定一个哨兵节点 prehead ，这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。然后，我们重复以下过程，直到 l1 或者 l2 指向了 null ：如果 l1 当前节点的值小于等于 l2 ，我们就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把 prev 向后移一位。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 创建一个新的链表，
        // 此时链表只有一个哨兵节点 prehead 和指向它自己的指针prev
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                // 哨兵节点末尾指向list1
                prev.next = list1;
                list1 = list1.next;
            } else {
                prev.next = list2;
                list2 = list2.next;
            }
            // 一轮迭代结束后
            // 移动指针，原来指向哨兵节点的指针
            // 现在指向list1和list2第一轮迭代中较小的节点
            prev = prev.next;
        }
        // 迭代结束后，直接将哨兵节点末尾指向未合并完的链表
        prev.next = list1 == null ? list2 : list1;
        return prehead.next;
    }
}