LeetCode Hot100刷题——合并两个有序链表
21.合并两个有序链表
1. 题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 <= 100l1和l2均按 非递减顺序 排列
2. 完整思路分析
题目要求：合并两个升序链表为一个新的升序链表，要求通过直接拼接节点实现（不创建新节点）。
核心思路：使用双指针遍历两个链表，比较节点值大小，将较小值的节点链接到新链表上。
- 关键技巧：
- 哨兵节点（Dummy Node）：简化链表头部的特殊处理，避免空指针问题。
- 指针移动策略：始终将较小值的节点接入新链表，并移动对应链表的指针。
- 剩余链表处理：当某一链表遍历完后，直接将另一链表的剩余部分接入新链表。
- 边界处理：
- 两个链表均为空时，返回空链表。
- 其中一个链表为空时，直接返回另一个链表。
时间复杂度：O(m+n)，其中m和n分别是两个链表的长度。
空间复杂度：O(1)，仅使用常熟级别的额外空间。
3. 解题过程
步骤分析：
- 创建一个哨兵节点（dummy），用于简化边界条件处理，它的next指向合并后链表的头节点。
- 使用一个指针current指向当前新链表的最后一个节点，初始时指向dummy。
- 使用两个指针分别指向两个链表的当前节点，初始时分别为l1和l2的头节点。
- 循环比较两个链表当前节点的值，将较小值的节点接在current后面，并移动该链表的指针和current指针。
- 当其中一个链表遍历完时，将另一个链表的剩余部分直接接在current后面（因为链表本身就是有序的）。
- 返回dummy.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) {// 创建哨兵节点，简化链表头处理ListNode dummy = new ListNode(-1);ListNode current = dummy;// 双指针遍历两个链表while (list1 != null && list2 != null) {if (list1.val <= list2.val) {// 将较小节点接入新链表current.next = list1;// 移动指针list1 = list1.next;} else {current.next = list2;list2 = list2.next;}// 更新新链表指针current = current.next;}// 处理剩余链表部分current.next = (list1 != null) ? list1 : list2;// 返回新链表的实际头节点return dummy.next;}
}
- 初始化哨兵节点
- 创建dummy节点（值为-1），其next指向最终结果链表的头部
- current指针初始指向dummy，用于构建新链表
- 双指针遍历比较
- 当 list1 和 list2 均不为空时循环：
- 比较 list1.val 和 list2.val
- 将较小值的节点链接到current.next
- 移动较小值节点所在链表的指针（list1或list2后移）
- current指针后移，保持指向新链表末尾
- 处理剩余链表
- 循环结束后，最多只有一个链表非空
- 直接将非空链表链接到current.next
- 返回结果
- 返回dummy.next（哨兵节点的下一个节点即新链表的实际头节点）