わたしの部屋

范围#

题型归纳#

题型： 链表双指针

题目特征： 两个链表都已经按非递减顺序排列，需要把所有节点重新串成一个有序链表。

解法： 每次比较两个链表当前节点的值，把较小的节点接到结果链表后面。

易错点： 处理空链表、确定新头节点、移动 pre 指针、最后接上剩余链表。

看到”两个链表都已有序、合并为一个有序链表”就是双指针扫描的信号。核心做法是先选出两个头中较小的作为新头，然后用 pre、cur1、cur2 三个指针同步推进；最容易出错的是循环体内漏写 pre = pre.next，或者循环结束后逐个处理剩余节点而不是直接整体接上。

题意#

给定两个按非递减顺序排列的链表 list1 和 list2，将它们合并成一个新的非递减链表并返回。

新链表由原来两个链表中的节点拼接而成，不需要创建新的节点。

示例#

示例 1：

输入： list1 = [1,2,4], list2 = [1,3,4]

输出： [1,1,2,3,4,4]

示例 2：

输入： list1 = [], list2 = []

输出： []

示例 3：

输入： list1 = [], list2 = [0]

输出： [0]

提示#

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

核心思路#

因为两个链表本身已经有序，所以只需要从两个链表的头节点开始比较，把较小的节点接到结果链表后面，被接走的链表指针向后移动一位，pre 始终指向结果链表的最后一个节点。

这里不使用虚拟头节点，而是先比较 head1 和 head2，选出较小的作为真正的头节点 head，再用 cur1 和 cur2 从各自起点开始扫描。

两个链表都有序，所以剩余部分的所有节点必然大于等于已合并部分的尾部——循环结束后直接整体接上，不需要逐个处理。

核心模板#

1
public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
2
    if (head1 == null || head2 == null) {
3
        return head1 == null ? head2 : head1;
4
    }
5

6
    // 谁小谁做头节点
7
    ListNode head = head1.val <= head2.val ? head1 : head2;
8
    ListNode cur1 = head.next;
9
    ListNode cur2 = head == head1 ? head2 : head1;
10
    ListNode pre = head;
11

12
    while (cur1 != null && cur2 != null) {
13
        // 谁小接谁
14
        if (cur1.val <= cur2.val) {
15
            pre.next = cur1;
16
            cur1 = cur1.next;
17
        } else {
18
            pre.next = cur2;
19
            cur2 = cur2.next;
20
        }
21
        pre = pre.next;
22
    }
23

24
    // 剩余部分直接整体接上
25
    pre.next = cur1 != null ? cur1 : cur2;
26
    return head;
27
}

变量角色#

head 是合并后链表的真正头节点，最终返回它；cur1 从选为头节点的那条链表的 head.next 开始走，cur2 从另一条链表的头节点开始走；pre 始终指向结果链表当前的尾节点，每接上一个新节点就跟着往后移动一位。

过程拆解#

1. 空链表特判：任一为空直接返回另一个，不进入主逻辑。
2. 选头节点：比较 head1.val 和 head2.val，较小的作为 head；cur1 从 head.next 出发，cur2 从另一条链表头出发。
3. 双指针扫描：cur1 和 cur2 都不为空时，把较小的接到 pre.next，对应指针后移，pre 跟着移动。
4. 收尾：循环结束后至少一条为空，把不为空的那条直接接到 pre.next。

易错点#

• 任一链表为空时要提前返回，不能让 cur2 = head == head1 ? head2 : head1 这行拿到 null 后继续参与比较。
• cur1 从 head.next 开始，而不是 head——head 已经是结果链表的头节点，不能再被扫描一次。

循环体内漏写 pre = pre.next

错误写法：

1
if (cur1.val <= cur2.val) {
2
    pre.next = cur1;
3
    cur1 = cur1.next;
4
} else {
5
    pre.next = cur2;
6
    cur2 = cur2.next;
7
}
8
// 漏写 pre = pre.next

为什么错：pre 始终停在第一个接入的节点，之后每轮都覆盖同一个 pre.next，最终结果链表只剩最后一次接上的那个节点，前面的全部丢失。

正确写法：

1
if (cur1.val <= cur2.val) {
2
    pre.next = cur1;
3
    cur1 = cur1.next;
4
} else {
5
    pre.next = cur2;
6
    cur2 = cur2.next;
7
}
8
pre = pre.next; // 关键：pre 跟着新接入的节点往后走

口诀

先选头，pre 跟着走，循环后剩余直接接。