[Feedback] Unsuitable list impementation / method signature for "876-Middle of the Linked List"

In Rust it's not possible to have:

  • an imutable reference and a mutable reference pointing to the same object
  • more than one mutable references to the same object

Therefore, it's not possible to properly implement the "slow/fast pointer" solution for "876-Middle of the Linked List".
The current list definition is:

head: Option<Box<ListNode>>
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

So it's not possible to have a mutable "slow" pointer and an immutable "fast" pointer, nor mutable "slow" and "fast" pointers. The current workaround is to clone the list, which leaves a bad taste in the mouth:

impl Solution {
    pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut fast = head.as_ref();
        let mut slow = head.as_ref();

        while let Some(node) = fast {
            match node.next.as_ref() {
                None => break,
                Some(fast_next) => {
                    fast = fast_next.next.as_ref();
                    slow = slow.unwrap().next.as_ref();
                }
            }
        }

        // this clones all the nodes after (and including) "slow"
        slow.map(|n| n.clone())
    }
}

It would have been much better if the method signature was:

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

or even

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

which would have avoided the issue

PS: The same applies to "19. Remove Nth Node From End of List"

Comments (1)