Rust每日一题(14)--实现数据结构--删除链表的倒数第 N 个结点

leetcode地址 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1:

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

难度: 中等

知识点

• 双指针扫描
• 所有权规则(否则编译很难通过)
• Option相关API

思路

1. 首先扫描一遍整个链表的长度，然后对删除第n个节点；为了避免第一个节点被删除时需要特别处理，增加一个dummy节点指向head节点。

// Definition for singly-linked list.
#[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
    }
  }
}

struct  Solution{

}

impl Solution {
    pub fn remove_nth_from_end(head:Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut dummy = Some(Box::new(ListNode{val:0,next: head.clone()}));
        let mut curr = &mut dummy;
        let mut count = 0;
        while let Some(node) = curr {
          curr = &mut node.next;
          count += 1;
        }
        println!("{}", count);
        curr = &mut dummy;
        for _ in 0..(count-n-1){
          curr = &mut curr.as_mut().unwrap().next;
        }
        curr.as_mut().unwrap().next = curr.as_mut().unwrap().next.as_mut().unwrap().next.take();
        return dummy.unwrap().next;
    }
}

fn main(){
    let list = vec![1,2,3,4,5];
    let mut head =  Some(Box::new(ListNode::new(list[0])));
    let mut curr = head.as_mut();
    for i in 1..list.len() {
        if let Some(mut node) = curr.take() {
            node.next = Some(Box::new(ListNode::new(list[i])));
            curr = node.next.as_mut();
        }
    }
    println!("{:?}", Solution::remove_nth_from_end(head,5));
}

2. 可以采用两个指针，第一个指针curr比第二个指针next_curr提前n个节点遍历，这样第一个指针遍历结束后，正好第二个指针遍历的位置就是待删除节点的前一个节点位置。

impl Solution {
    pub fn remove_nth_from_end(mut head:Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut dummy = Some(Box::new(ListNode{val:0,next: head.clone()}));
        let mut curr = &mut head;
        let mut next_curr = &mut dummy;
        // let mut count = 0;
        for _ in 0..n{
            curr = &mut curr.as_mut().unwrap().next;
        };

        while let Some(node) = curr.as_mut() {
            curr = &mut node.next;
            next_curr = &mut next_curr.as_mut().unwrap().next;
        }

        next_curr.as_mut().unwrap().next = next_curr.as_mut().unwrap().next.as_mut().unwrap().next.take();
        return dummy.unwrap().next;
    }
}