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)(只用常数额外指针)
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-21-合并两个有序链表
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 20] 有效的括号
下一篇
[Leetcode 23] 合并 K 个升序链表