CODEWITHSUNDEEP
rust
user3461311
user3461311

Reputation: 105

How to use two pointers to iterate a linked list in Rust?

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.

Upvotes: 7

Views: 5671

Answers (2)

Anton Kalinin
Anton Kalinin

Reputation: 21

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

Upvotes: 1

Silvio Mayolo
Silvio Mayolo

Reputation: 70297

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

Upvotes: 8

Related Questions