当前位置：首页 > news >正文

010 【入门】链表入门题目-合并两个有序链表

news 2025/6/28 9:44:12

🔗 合并两个有序链表 | [算法]-[中级]-[链表]

▶ JDK8+ | ⏱️ O(m+n)

核心代码实现

package class010;// 将两个升序链表合并为一个新的升序链表并返回
// 新链表是通过拼接给定的两个链表的所有节点组成的
// 测试链接 : https://leetcode.cn/problems/merge-two-sorted-lists/
public class MergeTwoLists {// 链表节点定义public static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}}class Solution {/*** 合并两个有序链表的迭代解法* 时间复杂度: O(m+n)，其中m和n分别是两个链表的长度* 空间复杂度: O(1)，只需要常数级别的指针空间* * @param head1 第一个链表的头节点* @param head2 第二个链表的头节点* @return 合并后链表的头节点*/public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {// 边界条件：如果任一链表为空，直接返回另一个链表if (head1 == null || head2 == null) {return head1 == null ? head2 : head1;}// 选择头节点值较小的链表作为新链表的头ListNode head = head1.val <= head2.val ? head1 : head2;// cur1指向已选择头部链表的下一个节点ListNode cur1 = head.next;// cur2指向另一个链表的头节点ListNode cur2 = head == head1 ? head2 : head1;// pre指针用于追踪新链表的当前末尾节点ListNode pre = head;// 遍历两个链表，直到其中一个到达末尾while (cur1 != null && cur2 != null) {if (cur1.val <= cur2.val) {pre.next = cur1; // 连接cur1节点cur1 = cur1.next; // 移动cur1指针} else {pre.next = cur2; // 连接cur2节点cur2 = cur2.next; // 移动cur2指针}pre = pre.next; // 移动pre指针到新末尾}// 将剩余的未处理节点连接到新链表末尾pre.next = cur1 != null ? cur1 : cur2;return head;}}
}

关联知识图谱

1. 算法思路可视化

2. 三指针策略图解

pre  → [ ] → [ ] → ...↑headcur1 → [ ] → [ ] → ...cur2 → [ ] → [ ] → ...

3. 递归解法对比

// [递归解法] 更简洁但空间复杂度为O(m+n)
public ListNode mergeTwoListsRecursive(ListNode l1, ListNode l2) {// 基本情况：如果一个链表为空，返回另一个链表if (l1 == null) return l2;if (l2 == null) return l1;// 递归合并：选择较小的头节点，并递归合并剩余部分if (l1.val < l2.val) {l1.next = mergeTwoListsRecursive(l1.next, l2);return l1;} else {l2.next = mergeTwoListsRecursive(l1, l2.next);return l2;}
}

行动指南

1. 优化与变体

[优化] 使用哨兵节点简化代码：

// [推荐] 使用哨兵节点简化边界处理
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(-1); // 哨兵节点ListNode current = dummy;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {current.next = l1;l1 = l1.next;} else {current.next = l2;l2 = l2.next;}current = current.next;}// 连接剩余部分current.next = l1 != null ? l1 : l2;return dummy.next;
}