Как использовать два указателя для перебора связанного списка в Rust?

Question

Я только начал изучать 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

Я понимаю, что нарушил правила проверки заемщика, которые я не могу вынестичто-то из неизменяемой ссылки, но как мне добиться реализации с двумя указателями?

Любые предложения помогут, заранее спасибо.

Answer 1

Вы совершенно правы, что ваша проблема в том, что вы пытаетесь что-то вывести из заемного объекта.Для начала давайте взглянем на вашу подпись.

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 уже является ссылкой, и мы возвращаем ссылку сейчас.

Runnable code:

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