image.png
题目解析
采用快慢指针，快指针先走 n 步，然后快慢指针同步走，直到快指针到底。
#[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
}
}
}
pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
// 快慢指针
let mut dummy = Some(Box::new(ListNode::new(0)));
dummy.as_mut().unwrap().next = head;
let mut fast = dummy.clone();
let mut slow = &mut dummy;
//移动快指针
for _ in 0..n{
fast = fast.unwrap().next;
}
//同时移动，直到快指针到底
while fast.as_ref().unwrap().next.is_some() {
fast = fast.unwrap().next;
slow = &mut slow.as_mut().unwrap().next;
}
//删除指针
slow.as_mut().unwrap().next = slow.as_mut().unwrap().next.as_mut().unwrap().next.clone();
return dummy.unwrap().next;
}
复杂度分析
时间复杂度: O(n)。
空间复杂度: O(n)，因为快指针重新 clone 了一份。如果是 java 的话是 O(1)。
