🔗 合并两个有序链表

题目来源：21. 合并两个有序链表 – 力扣（LeetCode）

📌 题目描述

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

• 不允许创建新节点，仅通过调整指针“拼接”原有节点。
• 链表按非递减顺序排列（允许相等）。

✅ 示例解析

示例 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 均按非递减顺序排列

💡 解法：虚拟头节点 + 双指针 —— O(m+n) 时间，O(1) 空间

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                p.next = list1;
                list1 = list1.next;
            } else {
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        if (list1 == null) {
            p.next = list2;
        }
        if (list2 == null) {
            p.next = list1;
        }
        return dummy.next;
    }
}

📊 复杂度分析

• 时间复杂度：O(m + n)
  • m、n 分别为两个链表长度，每个节点最多访问一次。
• 空间复杂度：O(1) ✅
  • 仅使用常数个额外指针，无递归、无哈希表。

🧩 解题思路

核心思想：双指针逐个比较 + 虚拟头节点统一处理

1. 边界处理：
   • 若任一链表为空，直接返回另一个链表。
2. 初始化：
   • 创建虚拟头节点 dummy，用于统一操作。
   • 使用指针 p 跟踪当前合并链表的尾部。
3. 主循环：
   • 比较 list1 和 list2 当前节点值。
   • 将较小者接到 p.next，对应链表指针前移。
   • p 同步前移。
4. 收尾处理：
   • 循环结束后，必有一个链表未遍历完。
   • 将剩余部分直接拼接到 p.next。
5. 返回结果：
   • dummy.next 即为合并后链表的真实头节点。

举例说明：

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

• 初始：p → dummy(-1)
• 第1轮：1(l1) vs 1(l2) → 取 l1 的 1 → p → 1
• 第2轮：2(l1) vs 1(l2) → 取 l2 的 1 → p → 1→1
• 第3轮：2 vs 3 → 取 l1 的 2 → p → 1→1→2
• 第4轮：4 vs 3 → 取 l2 的 3 → p → 1→1→2→3
• 第5轮：4 vs 4 → 取 l2 的 4 → p → 1→1→2→3→4
• l2 走完，l1 剩余 4 → 拼接 → p → ...→4→4
• 返回 dummy.next → [1,1,2,3,4,4] ✅

边界处理：

• 两个都为空 → 直接返回 null。
• 一个为空 → 返回另一个。
• 长度不等 → 循环后拼接剩余部分。