{"content":{"title":"Rust每日一题(14)--实现数据结构--删除链表的倒数第 N 个结点","body":"[leetcode地址](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/)\r\n给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。\r\n\r\n**示例 1:**\r\n```\r\n输入：head = [1,2,3,4,5], n = 2\r\n输出：[1,2,3,5]\r\n```\r\n**示例 2：**\r\n```\r\n输入：head = [1], n = 1\r\n输出：[]\r\n```\r\n**示例 3：**\r\n```\r\n输入：head = [1,2], n = 1\r\n输出：[1]\r\n```\r\n\r\n**难度: 中等**\r\n\r\n## 知识点\r\n- 双指针扫描\r\n- 所有权规则(否则编译很难通过)\r\n- Option相关API\r\n\r\n## 思路\r\n1. 首先扫描一遍整个链表的长度，然后对删除第n个节点；为了避免第一个节点被删除时需要特别处理，增加一个dummy节点指向head节点。\r\n```\r\n// Definition for singly-linked list.\r\n#[derive(PartialEq, Eq, Clone, Debug)]\r\npub struct ListNode {\r\n  pub val: i32,\r\n  pub next: Option<Box<ListNode>>\r\n}\r\n\r\nimpl ListNode {\r\n  #[inline]\r\n  fn new(val: i32) -> Self {\r\n    ListNode {\r\n      next: None,\r\n      val\r\n    }\r\n  }\r\n}\r\n\r\nstruct  Solution{\r\n\r\n}\r\n\r\nimpl Solution {\r\n    pub fn remove_nth_from_end(head:Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {\r\n        let mut dummy = Some(Box::new(ListNode{val:0,next: head.clone()}));\r\n        let mut curr = &mut dummy;\r\n        let mut count = 0;\r\n        while let Some(node) = curr {\r\n          curr = &mut node.next;\r\n          count += 1;\r\n        }\r\n        println!(\"{}\", count);\r\n        curr = &mut dummy;\r\n        for _ in 0..(count-n-1){\r\n          curr = &mut curr.as_mut().unwrap().next;\r\n        }\r\n        curr.as_mut().unwrap().next = curr.as_mut().unwrap().next.as_mut().unwrap().next.take();\r\n        return dummy.unwrap().next;\r\n    }\r\n}\r\n\r\nfn main(){\r\n    let list = vec![1,2,3,4,5];\r\n    let mut head =  Some(Box::new(ListNode::new(list[0])));\r\n    let mut curr = head.as_mut();\r\n    for i in 1..list.len() {\r\n        if let Some(mut node) = curr.take() {\r\n            node.next = Some(Box::new(ListNode::new(list[i])));\r\n            curr = node.next.as_mut();\r\n        }\r\n    }\r\n    println!(\"{:?}\", Solution::remove_nth_from_end(head,5));\r\n}\r\n```\r\n\r\n2. 可以采用两个指针，第一个指针`curr`比第二个指针`next_curr`提前n个节点遍历，这样第一个指针遍历结束后，正好第二个指针遍历的位置就是待删除节点的前一个节点位置。\r\n```\r\nimpl Solution {\r\n    pub fn remove_nth_from_end(mut head:Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {\r\n        let mut dummy = Some(Box::new(ListNode{val:0,next: head.clone()}));\r\n        let mut curr = &mut head;\r\n        let mut next_curr = &mut dummy;\r\n        // let mut count = 0;\r\n        for _ in 0..n{\r\n            curr = &mut curr.as_mut().unwrap().next;\r\n        };\r\n\r\n        while let Some(node) = curr.as_mut() {\r\n            curr = &mut node.next;\r\n            next_curr = &mut next_curr.as_mut().unwrap().next;\r\n        }\r\n\r\n        next_curr.as_mut().unwrap().next = next_curr.as_mut().unwrap().next.as_mut().unwrap().next.take();\r\n        return dummy.unwrap().next;\r\n    }\r\n}\r\n```"},"author":{"user":"https://learnblockchain.cn/people/720","address":null},"history":null,"timestamp":1673668557,"version":1}