我刚开始学习Rust lang,并尝试在Leetcode上进行一些练习。我正在解决链表中间的问题。
解决方案只是使用慢速和快速指针。这是我在Rust中的代码:
#[derive(PartialEq, Eq, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>
}
impl ListNode {
#[inline]
pub fn new(val: i32) -> Self {
ListNode {
next: None,
val
}
}
}
struct Solution;
impl Solution {
pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let slow = &head;
let fast = &head;
while fast.is_some() && fast.unwrap().next.is_some() {
slow = &(slow.unwrap().next);
fast = &(fast.unwrap().next.unwrap().next);
}
*slow
}
}
但是,我遇到了很多编译器错误,例如:
--> src/main.rs:22:33
|
22 | while fast.is_some() && fast.unwrap().next.is_some() {
| ^^^^ cannot move out of borrowed content
我知道我违反了借款人检查规则,无法从不可变的ref中删除某些内容,但是我应该如何实现这种两指针式实现?
任何建议都会有所帮助,在此先感谢。
完全正确,您的问题是您正在尝试将某些东西移出借用的对象。首先,让我们看一下您的签名。
pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
此功能获取head
列表的所有权并返回列表(列表的某些子列表)的所有权。毫无疑问,这不是您想要的,因为它会使对该列表的任何其他引用无效。在这种情况下,我们想借用该参数并返回另一个引用。
pub fn middle_node(head: &Option<Box<ListNode>>) -> &Option<Box<ListNode>> {
没有所有权易手。无需所有权就易手;呼叫者将在开始时拥有列表,而在结束时将拥有列表。
现在,您将分配给fast
和slow
,因此它们需要是可变的。你不能重新分配普通人let
。
let mut slow = head;
let mut fast = head;
(我还删除了&head
,因为head
现在已经是参考,因此我们不再需要引用。)
现在,终于,就像你说的,你想移动每一次,这既是不必要的,混乱的,以借检查值进行选择的。幸运的是,Option
提供了一种方便的方法来引用内部。as_ref
取一个Option<T>
并将其转换为Option<&T>
,这样我们就可以借用内部了。我们需要as_ref
在每次我们做之前unwrap
。例如,
while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
(请注意as_ref
),在所有其他地方,您都unwrap
可以选择相同的值。最后,返回的*slow
只是变为slow
,因为再次slow
已经是引用,我们现在正在返回引用。
可运行的代码:
#[derive(PartialEq, Eq, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>
}
impl ListNode {
#[inline]
pub fn new(val: i32) -> Self {
ListNode {
next: None,
val
}
}
}
struct Solution;
impl Solution {
pub fn middle_node(head: &Option<Box<ListNode>>) -> &Option<Box<ListNode>> {
let mut slow = head;
let mut fast = head;
while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
slow = &(slow.as_ref().unwrap().next);
fast = &(fast.as_ref().unwrap().next.as_ref().unwrap().next);
}
slow
}
}
fn arr_to_list(arr: &[i32]) -> Option<Box<ListNode>> {
let mut head = None;
for n in arr {
let mut new_node = ListNode::new(*n);
new_node.next = head;
head = Some(Box::new(new_node));
}
head
}
fn main() {
let node = arr_to_list(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
let mid = Solution::middle_node(&node);
println!("Middle node is {}", mid.as_ref().unwrap().val)
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句