1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112

//! Remove Nth Node From End of List [leetcode: remove_nth_node_from_end_of_list](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)
//!
//! Given a linked list, remove the *n*-th node from the end of list and return its head.
//!
//! **Example:**
//!
//! ```
//! Given linked list: 1->2->3->4->5, and n = 2.
//!
//! After removing the second node from the end, the linked list becomes 1->2->3->5.
//! ```
//!
//! **Note:**
//!
//! Given *n* will always be valid.
//!
//! **Follow up:**
//!
//! Could you do this in one pass?

/// # Solutions
///
/// # Approach 1: Two pass algorithm
///
/// * Time complexity: O(L)
///
/// * Space complexity: O(1)
///
/// ```rust
///
/// // 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>> {
///         let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
///         let mut cur = &mut dummy;
///         let mut length = 0;
///
///         while let Some(_node) = cur.as_mut() {
///             cur = &mut cur.as_mut().unwrap().next;
///             if let Some(_inner_node) = cur { length += 1; }
///         }
///
///         let mut new_cur = dummy.as_mut();
///         let idx = length - n;
///
///         for _ in 0..idx {
///             new_cur = new_cur.unwrap().next.as_mut();
///         }
///
///         let next = new_cur.as_mut().unwrap().next.as_mut().unwrap().next.take();
///         new_cur.as_mut().unwrap().next = next;
///
///         dummy.unwrap().next
///     }
/// }
/// ```
///
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 }));
    let mut cur = &mut dummy;
    let mut length = 0;

    while let Some(_node) = cur.as_mut() {
        cur = &mut cur.as_mut().unwrap().next;
        if let Some(_inner_node) = cur { length += 1; }
    }

    let mut new_cur = dummy.as_mut();
    let idx = length - n;

    for _ in 0..idx {
        new_cur = new_cur.unwrap().next.as_mut();
    }

    let next = new_cur.as_mut().unwrap().next.as_mut().unwrap().next.take();
    new_cur.as_mut().unwrap().next = next;

    dummy.unwrap().next
}

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

#[allow(dead_code)]
impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}