7

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.

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.

user3461311
  • 95
  • 1
  • 7

2 Answers2

6

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>> {

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.

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;

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

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() {

(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.

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)
}
Silvio Mayolo
  • 62,821
  • 6
  • 74
  • 116
  • Hi Silvio, really appreciate for your answer. I think the method signature **middle_node(head: &Option>) -> &Option>** is defined by Leetcode, I probably should report this bug to them. – user3461311 Jan 03 '19 at 21:40
  • Also, seems like Option.as_ref().unwrap() is a common use scenario, I would wonder why we don't have a method combine them together in the core library. Thanks. – user3461311 Jan 03 '19 at 21:43
  • In my experience, `unwrap` tends to be discouraged except in small programs like this. `Option` has a lot of other ways of peering into it that don't involve panicking (`unwrap_or`, `ok_or`, etc), all of which need the same `as_ref` call to ensure borrowing. – Silvio Mayolo Jan 03 '19 at 22:12
  • I agree with you that this should be reported to Leetcode if they really did defining an owning type signature for that function. It's possible that they simply did so for all the challenges without really thinking about it (easy to do if you're writing a challenge that's supposed to support several languages), and it should really be brought to their attention. – Silvio Mayolo Jan 03 '19 at 22:12
0

Based on great answer by Silvio Mayolo: in case we need to deal with borrowed object inside the method (Leetcode is still using that signature), we can use ref to node for finding right one and than consider cloning in the end:

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.clone()
    }
}
Anton Kalinin
  • 11
  • 1