19. 删除链表的倒数第 N 个结点

题目描述

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

解题思路

之前用dummy 重新构造新的链表来做的

#![allow(unused)]

fn main() {
struct Solution {}

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

impl Solution {
    pub fn remove_nth_from_end(mut head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut dummy = ListNode::new(-1);
        while let Some(mut x) = head {
            head = x.next;
            x.next = dummy.next;
            dummy.next = Some(x);
        }
        let mut ptr = &mut dummy;
        for _ in 1..n { ptr = ptr.next.as_deref_mut().unwrap() }
        let drop = ptr.next.take();
        ptr.next = drop?.next.take();
        head = dummy.next.take();
        while let Some(mut x) = head {
            head = x.next;
            x.next = dummy.next;
            dummy.next = Some(x);
        }
        dummy.next
    }
}
}

学习感想

双指针法这道题用safe rust没法写，因为需要同时持有链表的两个引用，并且头部的引用还必须是可变引用，这是没法做到的

#![allow(unused)]

fn main() {
struct Solution {}

// 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
    }
  }
}
impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        unsafe {
            let dummy = ListNode { val: -1, next: head };
            let mut ptr = &dummy;
            for _ in 0..n { ptr = ptr.next.as_deref()? }
            let mut ptr2 = &dummy as *const ListNode as *mut ListNode;
            while ptr.next.is_some() {
                ptr = ptr.next.as_deref()?;
                ptr2 = (*ptr2).next.as_deref()? as *const ListNode as *mut ListNode;
            }
            let mut rigoff = (*ptr2).next.take()?;
            let nxt = rigoff.next.take();
            (*ptr2).next = nxt;
            dummy.next
        }
    }
}
}

所以这就是我用unsafe的原因

Unsafe Superpowers

To switch to unsafe Rust, use the unsafe keyword and then start a new block that holds the unsafe code. You can take five actions in unsafe Rust that you can’t in safe Rust, which we call unsafe superpowers. Those superpowers include the ability to:

• Dereference a raw pointer
• Call an unsafe function or method
• Access or modify a mutable static variable
• Implement an unsafe trait
• Access fields of unions

It’s important to understand that unsafe doesn’t turn off the borrow checker or disable any other of Rust’s safety checks: if you use a reference in unsafe code, it will still be checked. The unsafe keyword only gives you access to these five features that are then not checked by the compiler for memory safety. You’ll still get some degree of safety inside of an unsafe block.