In Rust it's not possible to have:
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"