如何使用两个指针在 Rust 中迭代一个链表? [英] How to use two pointers to iterate a linked list in Rust?

问题描述

我刚开始学习 Rust lang 并尝试在 Leetcode 上做一些实践.我正在解决链接列表中间的问题.

I just started to learn Rust lang and tried to do some practices on Leetcode. I'm working the problem Middle of the Linked List.

解决办法就是使用慢指针和快指针.这是我在 Rust 中的代码:

The solution is just to use the slow and fast pointer. This is my code in 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
    }
}

但是，我遇到了很多编译器错误，例如:

However, I got a lot of complier errors like:

  --> src/main.rs:22:33
   |
22 |         while fast.is_some() && fast.unwrap().next.is_some() {
   |                                 ^^^^ cannot move out of borrowed content

我知道我违反了无法从不可变引用中取出某些内容的借用者检查规则，但是我应该如何实现这种双指针实现?

I understand that I violated the borrower check rules that I cannot take out something from an immutable ref, but how should I achieve this two-pointer implementation?

任何建议都会有所帮助，提前致谢.

Any suggestions will help, thanks in advance.

推荐答案

你说得对，你的问题是你试图从借来的对象中移出一些东西.首先，让我们看看你的签名.

You're exactly right that your problem is you're trying to move something out of a borrowed object. First, let's take a look at your signature.

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

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

This function is taking ownership of head and returning ownership of (some sublist of) the list. This is undoubtedly not what you want, because it would invalidate any other references to the list. In this case, we want to borrow the argument and return another reference.

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

没有所有权易手.并且没有所有权需要易手；调用者将在开始时拥有列表，并在结束时拥有列表.

No ownership changes hands. And no ownership needs to change hands; the caller will own the list at the start and it will own the list at the end.

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

Now, you assign to fast and slow, so they need to be mutable. You can't reassign to an ordinary let.

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

(我也去掉了&head，因为head现在已经是一个引用了，所以我们不需要再引用一个引用了)

(I also removed the &head, as head is now already a reference, so we don't need to take a ref anymore)

现在，最后，正如您所说的，您每次都试图移动该选项的值，这对于借用检查器来说既不必要又令人困惑.幸运的是，Option 提供了一种方便的方式来获取内部引用.as_ref 接受一个 Option 并把它变成一个 Option<&T>，所以我们可以借用里面.我们需要在每次解包之前as_ref.例如，

Now, finally, as you said, you are trying to move the value out of the option every time, which is both unnecessary and confusing to the borrow checker. Fortunately, Option provides a convenient way to take a reference to the inside. as_ref takes an Option<T> and turns it into a Option<&T>, so we can borrow the inside. We need to as_ref before each time that we unwrap. For example,

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

(注意as_ref)在所有其他地方你解包一个可选值也是一样的.最后，返回的 *slow 简单地变成了 slow，因为再次 slow 已经是一个引用，我们现在正在返回一个引用.

(Notice the as_ref) And the same thing in all of the other places you unwrap an optional value. Finally, the returned *slow simply becomes slow, since again slow is already a reference and we're returning a reference now.

可运行代码:

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

这篇关于如何使用两个指针在 Rust 中迭代一个链表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！