🧠 涉及两个有序链表的合并、排序问题

一句话结论：
👉 “谁小谁先走”。这就是拉链原理：同时遍历两条链表，比较当前头节点，较小的那个接在结果链表后面，然后向前走一步。

⭐ 核心逻辑
哨兵节点 (Dummy Node)：只要一个 dummy，用来挂接结果。

拉拉链 (Comparison)：while 循环同时检查两个链表，谁小就把谁接上，被接走的那个指针后移，没被接走的保持不动。

接余部 (Post-processing)：这是链表对比数组的巨大优势 —— 当一条链表遍历完，另一条链表剩下的部分不需要遍历，直接把指针指过去就行（因为剩下的肯定也是有序的）。

⭐ 模板

  1. 初始化

    //虚拟头节点（锚点）
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    //两个并行指针
    ListNode p1 = l1;
    ListNode p2 = l2;

  2. 循环处理(控制指针移动)

    //同时遍历，按规则选择
    while (p1 != null && p2 != null) {

    if (choose(p1, p2)) {
    tail.next = p1;
    p1 = p1.next;
    } else {
    tail.next = p2;
    p2 = p2.next;
    }

    tail = tail.next;
    }

    //接上剩余部分
    tail.next = (p1 != null) ? p1 : p2;

  3. 返回结果
    return dummy.next;

Notice:

1.最大的优势：接余部（不要写循环！）

这是链表对比数组最大的优势，也是这个模板最容易写“多余”的地方。

直接一个 if 把剩下的整条链表挂在后面。因为剩下的部分本身就是有序的，不需要再遍历。

✅ 正确（利用链表特性，O(1) 操作）
if (l1 != null) tail.next = l1;
if (l2 != null) tail.next = l2;

❌ 错误/低效（把链表当数组用了，O(N) 操作）
while (l1 != null) {
tail.next = l1;
l1 = l1.next;
tail = tail.next;
}

相关练习题

1. LeetCode 21. 合并两个有序链表

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

2. LeetCode 23. 合并 K 个升序链表

题意： 给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

3. LeetCode 148. 排序链表

题意： 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。