leetcode

Leetcode problem solutions
git clone https://git.sinitax.com/sinitax/leetcode
Log | Files | Refs | sfeed.txt

0019-remove-nth-node-from-end-of-list.rs (2711B)

      1/// 19. Remove Nth Node From End of List (Medium)
      2///
      3/// Given the head of a linked list, remove the nth node from the end of the
      4/// list and return its head.
      5///
      6/// *Example 1:*
      7///
      8///   *Input:* head = [1,2,3,4,5], n = 2
      9///   *Output:* [1,2,3,5]
     10///
     11/// *Example 2:*
     12///
     13///   *Input:* head = [1], n = 1
     14///   *Output:* []
     15///
     16/// *Example 3:*
     17///
     18///   *Input:* head = [1,2], n = 1
     19///   *Output:* [1]
     20///
     21/// *Constraints:*
     22///
     23///   * The number of nodes in the list is sz.
     24///   * 1 <= sz <= 30
     25///   * 0 <= Node.val <= 100
     26///   * 1 <= n <= sz
     27///
     28/// *Follow up:* Could you do this in one pass?
     29///
     30use leetcode::*;
     31
     32#[derive(PartialEq, Eq, Clone, Debug)]
     33pub struct ListNode {
     34    pub val: i32,
     35    pub next: Option<Box<ListNode>>,
     36}
     37
     38impl ListNode {
     39    #[inline]
     40    fn new(val: i32) -> Self {
     41        ListNode { next: None, val }
     42    }
     43}
     44
     45struct Solution {}
     46
     47impl Solution {
     48    pub fn remove_nth_from_end(mut head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
     49        let mut front: *mut Option<Box<ListNode>> = &mut head as *mut _;
     50        let mut back: *mut Option<Box<ListNode>> = std::ptr::null_mut();
     51        let mut depth = 0i32;
     52        while let Some(Some(cur)) = unsafe { front.as_mut() } {
     53            if let Some(Some(b)) = unsafe { back.as_mut() } {
     54                back = &mut b.next as *mut _;
     55            }
     56            front = &mut cur.next as *mut _;
     57            depth += 1;
     58            if depth == n {
     59                back = &mut head as *mut _;
     60            }
     61        }
     62        if let Some(b) = unsafe { back.as_mut() } {
     63            *b = b.as_mut().and_then(|b| b.next.take())
     64        }
     65        head
     66    }
     67}
     68
     69fn build_list(vec: Vec<i32>) -> Option<Box<ListNode>> {
     70    let mut head = None;
     71    let mut tail: *mut Option<Box<ListNode>> = (&mut head) as *mut _;
     72    for elem in vec {
     73        unsafe {
     74            let mut link = Box::new(ListNode::new(elem));
     75            let tail_next = (&mut link.next) as *mut _;
     76            tail.as_mut().unwrap().replace(link);
     77            tail = tail_next;
     78        }
     79    }
     80    head
     81}
     82
     83pub fn main() {
     84    println!(
     85        "{:?}",
     86        Solution::remove_nth_from_end(build_list(arg_into(1)), arg_into(2))
     87    )
     88}
     89
     90#[cfg(test)]
     91mod tests {
     92    use crate::build_list;
     93    use crate::ListNode;
     94    use crate::Solution;
     95    use leetcode::vi;
     96
     97    fn l(s: &str) -> Option<Box<ListNode>> {
     98        build_list(vi(s))
     99    }
    100
    101    #[test]
    102    fn test() {
    103        assert_eq!(
    104            Solution::remove_nth_from_end(l("[1,2,3,4,5]"), 2),
    105            l("[1,2,3,5]")
    106        );
    107        assert_eq!(Solution::remove_nth_from_end(l("[1]"), 1), l("[]"));
    108        assert_eq!(Solution::remove_nth_from_end(l("[1,2]"), 1), l("[1]"));
    109    }
    110}