如何使用两个指针迭代Rust中的链表?

用户名

我刚开始学习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中删除某些内容,但是我应该如何实现这种两指针式实现?

任何建议都会有所帮助,在此先感谢。

西尔维奥·梅奥洛(Silvio Mayolo)

完全正确,您的问题是您正在尝试将某些东西移出借用的对象。首先,让我们看一下您的签名。

pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {

此功能获取head列表的所有权并返回列表(列表的某些子列表)的所有权。毫无疑问,这不是您想要的,因为它会使对该列表的任何其他引用无效。在这种情况下,我们想借用该参数并返回另一个引用。

pub fn middle_node(head: &Option<Box<ListNode>>) -> &Option<Box<ListNode>> {

没有所有权易手。无需所有权就易手;呼叫者将在开始时拥有列表,而在结束时将拥有列表。

现在,您将分配给fastslow,因此它们需要是可变的。你不能重新分配普通人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] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章