时间戳

首页 > 解决方案 > 如何使用两个指针在 Rust 中迭代链表？

rust - 如何使用两个指针在 Rust 中迭代链表？

问题描述

我刚开始学习 Rust 语言，并尝试在 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 中取出某些东西，但是我应该如何实现这个两指针实现呢？

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

标签： rust

解决方案

你是完全正确的，你的问题是你试图从借来的物体中移出一些东西。首先，让我们看一下您的签名。

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

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

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

没有所有权易手。并且没有所有权需要易手；调用者将在开始时拥有该列表，并在最后拥有该列表。

现在，您分配给fastand slow，因此它们需要是可变的。您不能重新分配给普通的let.

let mut slow = head;
let mut fast = head;

（我还删除了&head, 因为head现在已经是参考，所以我们不再需要参考）

现在，最后，正如您所说，您每次都试图将值移出选项，这对借用检查器来说既不必要又令人困惑。幸运的是，Option它提供了一种方便的方法来获取里面的引用。as_ref把 anOption<T>变成 a Option<&T>，所以我们可以借用里面。我们需要as_ref在每次我们之前unwrap。例如，

while fast.is_some() && fast.as_ref().unwrap().next.is_some() {

（注意as_ref） 和所有其他地方一样，你unwrap是一个可选值。最后，返回的*slow只是变成slow，因为 againslow已经是一个引用，我们现在正在返回一个引用。

可运行代码：

#[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)
}

推荐阅读