leetcode/
remove_nth_node_from_end_of_list.rs

1//! # 19. 删除链表的倒数第N个节点
2//!
3//! 难度 中等
4//!
5//! 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
6//!
7//! ## 示例：
8//!
9//! 给定一个链表: `1->2->3->4->5`, 和 `n = 2`.
10//!
11//! 当删除了倒数第二个节点后，链表变为 `1->2->3->5`.
12//!
13//! ## 说明：
14//!
15//! 给定的 n 保证是有效的。
16//!
17//! ## 进阶：
18//!
19//! 你能尝试使用一趟扫描实现吗？
20//!
21//! See [leetcode](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)
22
23pub struct Solution;
24
25use crate::ListNode;
26
27impl Solution {
28    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
29        Self::unsafe_version(head, n)
30    }
31
32    fn unsafe_version(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
33        assert!(n > 0);
34
35        let mut dummy = Box::new(ListNode {
36            next: head,
37            val: 0,
38        });
39
40        let mut fast = &(*dummy) as *const ListNode;
41        for _ in 0..n {
42            unsafe {
43                fast = (*fast).next.as_deref()?;
44            }
45        }
46
47        let mut slow = &mut (*dummy) as *mut ListNode;
48        unsafe {
49            while let Some(f) = (*fast).next.as_deref() {
50                fast = f;
51                slow = (*slow).next.as_deref_mut().unwrap();
52            }
53            let to_delete = (*slow).next.take().unwrap();
54            (*slow).next = to_delete.next;
55        }
56
57        dummy.next
58    }
59}
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64    use crate::list;
65
66    #[test]
67    fn test() {
68        let cases = vec![
69            (vec![1,2,3,5], (list![1,2,3,4,5], 2)),
70            (vec![1,2,3,4], (list![1,2,3,4,5], 1)),
71            (vec![2,3,4,5], (list![1,2,3,4,5], 5)),
72
73            // invalid n = 0
74            // (vec![1,2,3,4,5], (list![1,2,3,4,5], 0)),
75        ];
76        let t = |v, n| ListNode::into_vec(Solution::remove_nth_from_end(v, n));
77        for (expect, (input, val)) in cases {
78            assert_eq!(expect, t(input, val));
79        }
80    }
81}
leetcode/remove_nth_node_from_end_of_list.rs

leetcode/
remove_nth_node_from_end_of_list.rs
