文章目录
题目
标题和出处
标题:合并两个有序链表
出处:21. 合并两个有序链表
难度
3 级
题目描述
要求
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。
示例
示例 1:
输入:
l1
=
[1,2,4],
l2
=
[1,3,4]
\texttt{l1 = [1,2,4], l2 = [1,3,4]}
l1 = [1,2,4], l2 = [1,3,4]
输出:
[1,1,2,3,4,4]
\texttt{[1,1,2,3,4,4]}
[1,1,2,3,4,4]
示例 2:
输入:
l1
=
[],
l2
=
[]
\texttt{l1 = [], l2 = []}
l1 = [], l2 = []
输出:
[]
\texttt{[]}
[]
示例 3:
输入:
l1
=
[],
l2
=
[0]
\texttt{l1 = [], l2 = [0]}
l1 = [], l2 = [0]
输出:
[0]
\texttt{[0]}
[0]
数据范围
- 两个链表的结点数目范围是 [0, 50] \texttt{[0, 50]} [0, 50]
- -100 ≤ Node.val ≤ 100 \texttt{-100} \le \texttt{Node.val} \le \texttt{100} -100≤Node.val≤100
- l1 \texttt{l1} l1 和 l2 \texttt{l2} l2 均按非递减顺序排列
解法一
思路和算法
如果两个链表都为空,则合并后的链表也为空。如果两个链表中有一个链表为空,则合并后的链表为另一个链表。这两种情况可以概括为:分别判断两个链表是否为空,如果其中一个链表为空,则返回另一个链表作为合并后的结果。
如果两个链表都不为空,则为了满足合并后的链表有序,合并后的链表的头结点应为两个链表的头结点中的值较小的结点,确定头结点之后,再对剩下的结点进行合并。
对于链表 l l l,用 l [ 0 ] l[0] l[0] 表示其头结点, l [ 1 : ] l[1:] l[1:] 表示除了头结点以外的部分,则合并操作可以表示成如下形式:
mergeTwoLists ( l 1 , l 2 ) = { l 1 [ 0 ] + mergeTwoLists ( l 1 [ 1 : ] , l 2 ) , l 1 [ 0 ] . val ≤ l 2 [ 0 ] . val l 2 [ 0 ] + mergeTwoLists ( l 1 , l 2 [ 1 : ] ) , l 1 [ 0 ] . val > l 2 [ 0 ] . val \text{mergeTwoLists}(l_1, l_2) = \begin{cases} l_1[0] + \text{mergeTwoLists}(l_1[1:], l_2), & l_1[0].\textit{val} \le l_2[0].\textit{val} \\ l_2[0] + \text{mergeTwoLists}(l_1, l_2[1:]), & l_1[0].\textit{val} > l_2[0].\textit{val} \end{cases} mergeTwoLists(l1,l2)={l1[0]+mergeTwoLists(l1[1:],l2),l2[0]+mergeTwoLists(l1,l2[1:]),l1[0].val≤l2[0].vall1[0].val>l2[0].val
根据上述表示形式,合并操作是一个递归的过程。
递归的终止条件是两个链表中至少有一个链表为空,如果其中一个链表为空,则返回另一个链表作为合并后的结果。
如果两个链表都不为空,则可以调用上述递归完成链表的合并。
代码
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else {
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
}
复杂度分析
-
时间复杂度: O ( m + n ) O(m + n) O(m+n),其中 m m m 和 n n n 分别是两个链表的长度。合并过程中最多需要遍历两个链表中的每个结点一次。
-
空间复杂度: O ( m + n ) O(m + n) O(m+n),其中 m m m 和 n n n 分别是两个链表的长度。空间复杂度主要取决于递归调用栈的深度,递归调用栈最多不会超过 m + n m + n m+n 层。
解法二
思路和算法
也可以使用迭代的方法合并链表。当两个链表都不为空时,比较两个链表的对应结点值,将值较小的结点合并到结果链表中,然后将对应链表的结点向后移动一步。如果一个链表为空,或者遍历完毕,则将另一个链表的剩下的部分合并到结果链表中。
由于合并后的链表的头结点需要通过比较两个链表的头结点决定,因此需要创建哑结点 dummyHead \textit{dummyHead} dummyHead,将合并的结点依次添加到哑结点的后面。具体做法是,创建指针 temp \textit{temp} temp 表示上一个合并的结点,初始时 temp \textit{temp} temp 指向 dummyHead \textit{dummyHead} dummyHead,每次合并结点时,将合并的结点添加到 temp \textit{temp} temp 的后面,然后将 temp \textit{temp} temp 向后移动一步,直到合并完毕。合并结束之后, dummyHead . next \textit{dummyHead}.\textit{next} dummyHead.next 即为合并后的新链表的头结点。
下图为一个迭代合并链表的例子。灰色表示哑结点,黄色表示两个链表中遍历到的结点,绿色表示 temp \textit{temp} temp 指向的结点。
代码
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode temp = dummyHead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
temp.next = l1;
l1 = l1.next;
} else {
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
if (l1 != null) {
temp.next = l1;
} else {
temp.next = l2;
}
return dummyHead.next;
}
}
复杂度分析
-
时间复杂度: O ( m + n ) O(m + n) O(m+n),其中 m m m 和 n n n 分别是两个链表的长度。合并过程中最多需要遍历两个链表中的每个结点一次。
-
空间复杂度: O ( 1 ) O(1) O(1)。