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;
    }
}