【LeetHOT100】合并两个有序链表——Java多解法详解

一、题目描述21. 合并两个有序链表将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 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 100list1和list2均按非递减顺序排列二、解题思路概览合并两个有序链表最自然的想法是使用双指针归并。常见解法有三种解法时间复杂度空间复杂度特点迭代归并O(mn)O(1)最优解面试首选递归归并O(mn)O(mn)栈空间代码简洁思路清晰集合排序法O((mn) log(mn))O(mn)不推荐仅作对比三、解法一迭代归并推荐⭐3.1 思路同时遍历两个链表比较当前节点值将较小者接入结果链表并移动对应链表的指针。最后将未遍历完的链表直接接到结果末尾。3.2 代码实现javaclass Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 哑结点简化边界处理 ListNode dummy new ListNode(0); ListNode cur dummy; while (list1 ! null list2 ! null) { if (list1.val list2.val) { cur.next list1; list1 list1.next; } else { cur.next list2; list2 list2.next; } cur cur.next; } // 连接剩余部分 cur.next (list1 ! null) ? list1 : list2; return dummy.next; } }3.3 图解示例以list1 [1,2,4]list2 [1,3,4]为例text初始: list1: 1 → 2 → 4 list2: 1 → 3 → 4 dummy → null 第1步: 比较1和1取list1的1 → dummy → 1, list1指向2 第2步: 比较2和1取list2的1 → dummy → 1 → 1, list2指向3 第3步: 比较2和3取list1的2 → ... → 2, list1指向4 第4步: 比较4和3取list2的3 → ... → 3, list2指向4 第5步: 比较4和4取list1的4 → ... → 4, list1指向null 最后: 将list2剩余的4接上 → 得到 1→1→2→3→4→43.4 复杂度分析时间复杂度O(mn)每个节点恰好被处理一次。空间复杂度O(1)只使用了常数个指针。四、解法二递归归并4.1 思路递归定义合并两个链表的结果 较小头节点 合并剩余部分。递归终止条件任一链表为空返回另一个链表。4.2 代码实现javaclass Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if (list1 null) return list2; if (list2 null) return list1; if (list1.val list2.val) { list1.next mergeTwoLists(list1.next, list2); return list1; } else { list2.next mergeTwoLists(list1, list2.next); return list2; } } }4.3 复杂度分析时间复杂度O(mn)每个节点被递归调用一次。空间复杂度O(mn)递归调用栈的深度等于合并后链表的长度。4.4 递归与迭代对比维度迭代递归代码长度稍长极简空间效率O(1)O(n)可读性直观需要理解递归风险无链表过长可能栈溢出五、解法三集合排序法不推荐5.1 思路将两个链表的所有节点值取出放入ArrayList排序后再重新构建链表。这种方法完全没有利用链表已有序的特性效率低下仅作为错误代码对照。5.2 常见错误写法及修正错误代码来自用户提问javaclass Solution { ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListInteger list new ArrayList(); for(ListNode pre list1; pre ! null; pre pre.next) list.add(pre.val); for(ListNode pre list2; pre ! null; pre pre.next) list.add(pre.val); ArrayListInteger listsort new ArrayList(list); Collections.sort(listsort); // 对 listsort 排序 ListNode head new ListNode(0); ListNode cur head; for(int i 0; i list.size(); i) { // ❌ 错误用了未排序的 list cur.next new ListNode(list.get(i)); cur cur.next; } return head.next; } }错误原因排序的是listsort构建链表时却用了原始的list导致输出顺序仍为“先list1后list2”。正确修正但仍不推荐javaclass Solution { ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListInteger list new ArrayList(); for (ListNode p list1; p ! null; p p.next) list.add(p.val); for (ListNode p list2; p ! null; p p.next) list.add(p.val); Collections.sort(list); // 直接排序原列表 ListNode dummy new ListNode(0); ListNode cur dummy; for (int val : list) { cur.next new ListNode(val); cur cur.next; } return dummy.next; } }复杂度时间 O((mn) log(mn))空间 O(mn)。远不如归并法面试时请勿使用。六、解法对比与总结方法时间复杂度空间复杂度是否利用有序性面试推荐度迭代归并O(mn)O(1)✅⭐⭐⭐⭐⭐递归归并O(mn)O(mn)✅⭐⭐⭐⭐集合排序O(n log n)O(n)❌⭐6.1 面试建议首选迭代归并空间 O(1)最符合面试官期待。递归可作为备选代码简洁但要说明空间代价。切忌使用排序法即便能通过也会被质疑基本功。6.2 常见扩展问题合并 K 个有序链表LeetCode 23可使用分治归并或优先队列。合并后仍然保持有序本题已要求注意处理相等值时的稳定性通常无影响。不允许创建新节点必须原地拼接迭代法天然满足。七、相关链接题目链接21. 合并两个有序链表 - 力扣LeetCode官方题解合并两个有序链表官方题解