Function leetcode_for_rust::cd0019_remove_nth_node_from_end_of_list::remove_nth_from_end

pub fn remove_nth_from_end(
    head: Option<Box<ListNode>>, 
    n: i32
) -> Option<Box<ListNode>>

Solutions

Approach 1: Two pass algorithm

• Time complexity: O(L)

• Space complexity: O(1)

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
        let mut cur = &mut dummy;
        let mut length = 0;

        while let Some(_node) = cur.as_mut() {
            cur = &mut cur.as_mut().unwrap().next;
            if let Some(_inner_node) = cur { length += 1; }
        }

        let mut new_cur = dummy.as_mut();
        let idx = length - n;

        for _ in 0..idx {
            new_cur = new_cur.unwrap().next.as_mut();
        }

        let next = new_cur.as_mut().unwrap().next.as_mut().unwrap().next.take();
        new_cur.as_mut().unwrap().next = next;

        dummy.unwrap().next
    }
}