type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接两个链表的节点组成的。
示例 1：
示例 2：
示例 3：
提示：
- 两个链表的节点数目范围是
[0, 50]
100 <= Node.val <= 100
l1和l2均按 非递减顺序 排列
解法一：递归
- Base Case: 如果一个链表为空，直接返回另一个链表。
- 每一层递归比较
head1.val与head2.val，返回“当前较小的节点”，并且把它的next指向下一层递归的结果。
例子：
l1 = 1 → 4， l2 = 2 → 3- 比较 1 和 2 → 1 小 → 返回节点 1，并且
1.next = mergeTwoLists(4, 2→3)
- 下一层比较 4 和 2 → 2 小 → 返回节点 2，并且
2.next = mergeTwoLists(4, 3)
- 下一层比较 4 和 3 → 3 小 → 返回节点 3，并且
3.next = mergeTwoLists(4, None)
- l2 空了 → 返回节点 4。
最终拼接结果：1 → 2 → 3 → 4。
复杂度
- 时间：
O(m + n)（每个节点恰好处理一次）
- 空间：
O(m + n)（递归层数最多为m+n）
解法二：迭代 + dummy head
链表的迭代通常会建立一个“哨兵节点”（
dummy）和 一个结果链表，然后用一个指针不断往后接新节点，最后返回哨兵的 next。用一个
tail 指针表示当前已经合并好的结果链表的尾巴，一开始让它指向dummy节点。双指针同时扫描
l1、l2，每次取较小的挂到 tail.next，并移动该链表指针；最后把尚未耗尽的那条链表整体接到
tail.next；返回
dummy.next 即可。复杂度
- 时间：
O(m + n)
- 空间：
O(1)（只用常数额外指针）
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-21-合并两个有序链表
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 20] 有效的括号
下一篇
[Leetcode 23] 合并 K 个升序链表