.jpg)
566 字
3 分钟
合并两个有序链表
.jpg)
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路
- 迭代法：
- 创建哑节点(dummy)作为新链表头部
- 维护指针遍历两个链表
- 比较节点值，将较小节点链接到新链表
- 当一个链表耗尽时，链接另一链表剩余部分
- 递归法：
- 比较两链表头节点
- 较小节点作为新头节点
- 递归合并剩余部分
- 返回新头节点指针
关键洞察
- 哑节点技巧：简化链表头处理，避免空指针异常
- 尾指针优化：仅需维护当前指针，无需额外空间
- 链表无损性：操作指针而非创建新节点
- 递归基准：当任一链表空时直接返回另一链表
- 有序性利用：只需顺序比较，无需回溯扫描
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 迭代法 | O(n+m) | O(1) |
| 递归法 | O(n+m) | O(n+m) (递归栈) |
注：n 和 m 分别为两个链表的长度
代码实现
迭代法
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} list1 * @param {ListNode} list2 * @return {ListNode} */var mergeTwoLists = function (list1, list2) { const dummy = new ListNode() let temp = dummy, temp1 = list1, temp2 = list2
while (temp1 && temp2) { if (temp1.val <= temp2.val) { temp.next = temp1 temp1 = temp1.next } else { temp.next = temp2 temp2 = temp2.next } temp = temp.next }
temp.next = temp1 || temp2;
return dummy.next}递归法
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} list1 * @param {ListNode} list2 * @return {ListNode} */const mergeTwoLists = (list1, list2) => { // 基准情况：任一链表空时返回另一链表 if (!list1) return list2; if (!list2) return list1;
// 比较头节点 if (list1.val <= list2.val) { list1.next = mergeTwoLists(list1.next, list2); return list1; } else { list2.next = mergeTwoLists(list1, list2.next); return list2; }};