LeetCode经典题解：21、合并两个有序链表
合并两个有序链表：用“哨兵+双指针”轻松搞定（附记忆口诀）
合并两个有序链表是链表操作的经典题，也是面试高频考点。这道题的解法思路清晰，只要记住“哨兵站岗+双指针赛跑”的场景，代码就能信手拈来。本文用最通俗的方式拆解最优解法，看完就能懂，面试不慌。
一、问题理解：什么是“合并两个有序链表”？
给你两个升序排列的链表（比如 1→2→4 和 1→3→4），要求把它们合并成一个新的升序链表（结果应为 1→1→2→3→4→4）。
核心要求：
- 新链表中的节点要按从小到大顺序排列
- 不能创建新节点，只能调整原节点的
next指针
二、最优解法：哨兵+双指针（迭代法）
合并有序链表的关键是“比较两个链表的当前节点，取小的那个接在新链表后面”。用“哨兵节点”和“双指针”配合，能完美实现这个逻辑。
场景联想：“哨兵站岗+双指针赛跑”
想象两个链表是两条有序的队伍（比如队伍A：1→2→4，队伍B：1→3→4），现在要把它们合并成一条有序队伍：
- 哨兵（dump）：站在新队伍的最前面“站岗”，负责固定新链表的起点（方便最后返回结果）。
- 当前指针（cur）：从哨兵身后开始，负责“连接”下一个节点（相当于新队伍的“尾部”）。
- 双指针（list1, list2）：分别指向两个原队伍的当前排头，谁小就把谁“拉”到新队伍后面。
3步口诀：“比大小，接尾巴，指针移”
重复以下步骤，直到其中一个队伍空了：
- 比大小：比较两个队伍排头的大小（
list1.val和list2.val）。 - 接尾巴：把小的那个节点接到新队伍的尾部（
cur.next = 小节点）。 - 指针移：被接走的队伍排头后移（
list1 = list1.next或list2 = list2.next），新队伍尾部也后移（cur = cur.next）。
最后，把剩下的队伍直接接在新队伍后面（因为剩下的节点已经是有序的）。
三、代码实现（附步骤拆解）
用代码实现上述逻辑，就像按剧本演戏一样自然：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 1. 哨兵节点：站在新链表最前面，固定起点ListNode dump = new ListNode(0);// 当前指针：从哨兵身后开始，负责连接节点ListNode cur = dump;// 2. 双指针赛跑：两个队伍都有人时，比较大小while (list1 != null && list2 != null) {if (list1.val < list2.val) {// 把list1的当前节点接在新队伍后面cur.next = list1;// list1队伍排头后移list1 = list1.next;} else {// 把list2的当前节点接在新队伍后面cur.next = list2;// list2队伍排头后移list2 = list2.next;}// 新队伍尾部后移cur = cur.next;}// 3. 接剩下的队伍：剩下的节点已经有序，直接接在后面cur.next = (list1 != null) ? list1 : list2;// 返回哨兵后面的节点，就是合并后的新链表return dump.next;}
}
四、面试时怎么快速回忆？
记住这4个关键点，代码就能“推导”出来：
- 哨兵初始化：
ListNode dump = new ListNode(0); ListNode cur = dump;（哨兵站岗，cur从哨兵后开始）。 - 循环条件：
while (list1 != null && list2 != null)（两个队伍都有人时继续）。 - 循环内3步：
- 比大小：
if (list1.val < list2.val) - 接尾巴：
cur.next = 小节点 - 指针移：
小节点指针后移; cur = cur.next
- 比大小：
- 收尾操作：
cur.next = 剩下的非空链表，返回dump.next。
五、为什么这是最优解？
- 时间复杂度：O(n+m)，n和m是两个链表的长度，每个节点只遍历一次。
- 空间复杂度：O(1)，只用到3个指针（
dump/cur/list1/list2），没有额外占用空间。 - 逻辑直观：用“队伍合并”场景就能解释，面试官一眼就能理解你的思路。
总结
合并两个有序链表的核心是“哨兵固定起点，双指针比较大小，小的接在新链表后面”。记住“哨兵站岗+双指针赛跑”的场景和“比大小，接尾巴，指针移”的口诀，代码就像填空一样简单。面试前用 1→2→4 和 1→3→4 手动模拟一遍，肌肉记忆就有了，轻松拿下这道题！