YSMull
<-- algorithm



原题链接

用 rust 写链表的题目还是比较痛苦的。

不引入哨兵节点

impl Solution {
    pub fn remove_nth_from_end(mut head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut k = 0;
        let mut p = head.as_ref().unwrap();
        // 先让第一个节点走 n 次
        while k < n && p.next.is_some() {
            p = p.next.as_ref().unwrap();
            k = k + 1;
        }

        // 还没有走 n 次就到头了,说明 n 大于等于链表的长度,要删除的其实是头结点
        if k < n {
            return head.unwrap().next;
        }
        // head 已经有了非可变借用,不能改变,因此 clone 一个新的,但这里深拷贝了整个链表
        let mut head = head.clone();
        let mut q = head.as_mut().unwrap();
        while p.next.is_some() {
            p = p.next.as_ref().unwrap();
            q = q.next.as_mut().unwrap();
        }
        // 此时 q 指向了待删除元素的前一个结点
        q.next = q.next.as_ref().unwrap().next.clone();
        return head;
    }
}

引入哨兵节点

impl Solution {
    pub fn remove_nth_from_end(mut head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut dummy = ListNode::new(0);
        dummy.next = head.take();
        let mut k = 0;
        let mut p = &dummy;
        // 先让第一个节点走 n 次
        while k < n {
            p = p.next.as_ref().unwrap();
            k = k + 1;
        }
        // 这里之所以要 clone 一个新的 dummy 是因为旧的 dummy 已经有非可变借用,已经不可变了,但这里深拷贝了整个链表
        let mut dummy = dummy.clone();
        let mut q: &mut ListNode = &mut dummy;
        while p.next.is_some() {
            p = p.next.as_ref().unwrap();
            q = q.next.as_mut().unwrap();
        }
        // 此时 q 指向了待删除元素的前一个结点
        q.next = q.next.as_mut().unwrap().next.take();
        return dummy.next;
    }
}