data structures - Is there a way to make an immutable reference mutable?

Question

I want to solve a leetcode question in Rust (Remove Nth Node From End of List). My solution uses two pointers to find the Node to remove:

#[derive(PartialEq, Eq, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

// two-pointer sliding window
impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut dummy_head = Some(Box::new(ListNode { val: 0, next: head }));
        let mut start = dummy_head.as_ref();
        let mut end = dummy_head.as_ref();
        for _ in 0..n {
            end = end.unwrap().next.as_ref();
        }
        while end.as_ref().unwrap().next.is_some() {
            end = end.unwrap().next.as_ref();
            start = start.unwrap().next.as_ref();
        }
        // TODO: fix the borrow problem
        // ERROR!
        // start.unwrap().next = start.unwrap().next.unwrap().next.take();
        dummy_head.unwrap().next
    }
}

I borrow two immutable references of the linked-list. After I find the target node to remove, I want to drop one and make the other mutable. Each of the following code examples leads to a compiler error:

// ERROR
drop(end); 
let next = start.as_mut().unwrap.next.take();

// ERROR
let mut node = *start.unwrap()

I don't know if this solution is possible to be written in Rust. If I can make an immutable reference mutable, how do I do it? If not, is there anyway to implement the same logic while making the borrow checker happy?

Answer 1

Is there a way to make an immutable reference mutable?

No.

You could write unsafe Rust code to force the types to line up, but the code would actually be unsafe and lead to undefined behavior. You do not want this.

---

For your specific problem, see:

• How to remove the Nth node from the end of a linked list?
• How to use two pointers to iterate a linked list in Rust?