21. 合并两个有序链表

✨核心逻辑

本题采用 双指针（迭代） 的策略：

虚拟头节点（Dummy Node）：为了方便处理结果链表为空的情况，以及简化头部节点的拼接操作，我们创建一个虚拟头节点 dummy。
双指针穿针引线：使用一个工作指针 curr 始终指向结果链表的最后一个节点。当两个链表都非空时，比较它们当前节点的值。
节点拼接：
- 如果 list1.val 小于 list2.val，就把 list1 当前节点接到 curr.next 后面，并将 list1 指针后移。
- 反之，则把 list2 当前节点接过去，并将 list2 指针后移。
- 每次拼接后，curr 指针也要同步后移，指向新链表的尾部。
收尾处理：当 while 循环结束时，必定有一条链表已经遍历完。此时，直接将另一条尚未遍历完的链表剩余部分，整体拼接到 curr.next 后面即可。

🔥代码实现（含详细变量注释）

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // dummy：虚拟头节点（哑节点），不存储实际数值，它的 next 指向结果链表的真实头节点
        ListNode dummy = new ListNode(-1);
        // curr：工作指针，始终指向当前合并后新链表的最后一个节点，初始指向 dummy
        ListNode curr = dummy;

        // 当两个链表都还有节点未遍历完时，进行循环比较
        while (list1 != null && list2 != null) {
            // 比较两个链表当前节点的值，将较小值的节点拼接到结果链表末尾
            if (list1.val < list2.val) {
                curr.next = list1;       // 将 list1 的当前节点接入结果链表
                curr = curr.next;        // curr 指针向后移动
                list1 = list1.next;      // list1 指针向后移动
            } else {
                curr.next = list2;       // 将 list2 的当前节点接入结果链表
                curr = curr.next;        // curr 指针向后移动
                list2 = list2.next;      // list2 指针向后移动
            }
        }

        // 循环结束后，如果 list1 还没走完（说明 list2 已经空了），
        // 直接将剩余的 list1 整体拼接在 curr 后面
        if (list1 != null) {
            curr.next = list1;
        }
        // 如果 list2 还没走完（说明 list1 已经空了），
        // 直接将剩余的 list2 整体拼接在 curr 后面
        if (list2 != null) {
            curr.next = list2;
        }
        
        // 返回虚拟头节点的下一个节点，即合并后链表的真正头节点
        return dummy.next;
    }
}

⏱️复杂度分析
- 时间复杂度：O(M + N)，其中 M 和 N 分别是两个链表的长度。我们只需遍历两个链表一次，每一轮迭代都处理其中一个节点，总循环次数为 M + N。
- 空间复杂度：O(1)，我们仅仅使用了 dummy 和 curr 两个额外的指针变量，没有创建新的链表节点，完全是原地拼接，空间开销是常数级的。