21.合并两个有序链表

题目:21.合并两个有序链表

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

• 示例 1：

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

• 示例 2：

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

• 示例 3：

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

• 提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

思路

将两个升序链表合并为一个新的升序链表可以通过使用 归并 的思想来实现。我们将两个链表进行逐步比较，每次选择较小的节点添加到新链表中，直到其中一个链表遍历完为止。然后，将剩余的节点直接附加到新链表的末尾。

1. 伪头节点初始化: 创建一个伪头节点 (result) ，它帮助我们轻松地处理链表头的情况。

2. 比较节点: 在两个链表 l1 和 l2 上同时遍历，比较每个节点的值。将较小的节点附加到新链表中，并移动相应链表的指针。

3. 处理剩余节点: 在其中一个链表遍历完后，直接将另一个链表的剩余部分附加到新链表末尾。

4. 返回结果: 最后返回伪头节点 (result) 的下一个节点，即结果链表的头节点。

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

代码

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode result = new ListNode(0);
    ListNode current = result;
    while (list1 != null && list2 != null) {
        int x = list1.val;
        int y = list2.val;
        if (x <= y) {
            current.next = new ListNode(x);
            // 移动到下一个节点
            list1 = list1.next;
        } else {
            current.next = new ListNode(y);
            // 移动到下一个节点
            list2 = list2.next;

        }
        current = current.next;
    }
    if (list1 != null) {
        current.next = list1;
    } else {
        current.next = list2;
    }
    return result.next;
}