2020/2/17
题目描述
- 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
相关标签
链表
解题思路
递归法
算法：
特殊的，如果 l1 或者 l2 一开始就是 null ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个的头元素更小，然后递归地决定下一个添加到结果里的值。如果两个链表都是空的，那么过程终止，所以递归过程最终一定会终止。
复杂度分析：
时间复杂度：O(n+m)，递归过程中会遍历两个链表中的所有元素，所以时间复杂度与合并后的链表长度呈线性关系
空间复杂度：O(n+m)，由于采用递归，需要 n + m 次函数调用，消耗掉 O(n+m)的空间。迭代法
算法
采用迭代的前提条件是 l1 的首个节点小于 l2 的首个节点。
依次判断 l2 的值是否处于 l1 的两个节点之间，如果是便插入该 l2 节点， 每次迭代 l1 的指针右移一位。当l1到尾部之后，直接将 l2 剩余的部分接在 l1 后面。
复杂度分析
时间复杂度：O(n+m)，遍历总次数大致为 n+m 次，每次迭代的时间为常数级。
空间复杂度：O(1)。迭代的过程中只会需要几个指针的常数级别的空间。
源代码
递归法
// 递归法
pub fn merge_two_lists(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
match (l1, l2) {
(None, None) => None,
(None, r) => r,
(l, None) => l,
(Some(mut l), Some(mut r)) => {
if l.val <= r.val {
l.next = Self::merge_two_lists(l.next, Some(r));
Some(l)
} else {
r.next = Self::merge_two_lists(Some(l), r.next);
Some(r)
}
}
}
}
- 执行用时 : 0 ms, 在所有 Rust 提交中击败了100.00%的用户
- 内存消耗 : 2.0 MB, 在所有 Rust 提交中击败了50.00%的用户
迭代法
//迭代法
impl Solution {
pub fn merge_two_lists(mut l1: Option<Box<ListNode>>, mut l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut head = Some(Box::new(ListNode::new(0)));
let (mut p1, mut p2, mut pr) = (&mut l1 as *mut Option<Box<ListNode>>,
&mut l2 as *mut Option<Box<ListNode>>,
&mut head as *mut Option<Box<ListNode>>);
unsafe {
let node_val = |x: *mut Option<Box<ListNode>>| {
if *x == None {
None
}else {
Some((*x).as_ref().unwrap().val)
}
};
let node_next = |x: *mut Option<Box<ListNode>>| {
if *x == None {
x
}else {
&mut (*x).as_mut().unwrap().next as *mut Option<Box<ListNode>>
}
};
loop {
match (node_val(p1), node_val(p2)) {
(Some(v1), Some(v2)) => {
if v1 < v2 {
if (*node_next(pr)) != None && node_next(pr) == p2 {
l2 = (*node_next(pr)).take();
p2 = &mut l2 as *mut Option<Box<ListNode>>;
}
(*node_next(pr)) = (*p1).take();
pr = node_next(pr);
p1 = node_next(pr);
}else {
if (*node_next(pr)) != None && node_next(pr) == p1 {
l1 = (*node_next(pr)).take();
p1 = &mut l1 as *mut Option<Box<ListNode>>;
}
(*node_next(pr)) = (*p2).take();
pr = node_next(pr);
p2 = node_next(pr);
};
},
(Some(_), None) => {
(*pr).as_mut().unwrap().next = (*p1).take();
break;
},
(None, Some(_)) => {
(*pr).as_mut().unwrap().next = (*p2).take();
break;
},
(None, None) => {
return None;
},
}
}
}
head.unwrap().next
}
}
- 执行用时 : 0 ms, 在所有 Rust 提交中击败了100.00%的用户
- 内存消耗 : 1.9 MB, 在所有 Rust 提交中击败了83.33%的用户
总结
迭代法相比递归法可以省去一些空间，但是代码量会大上不少。链表相关的操作，尤其是要用到双指针的时候，可以考虑使用unsafe，能省去不少事情。option的take()方法也尤其重要。
