19. Remove Nth Node From End of List Medium

1/**
2 * [19] Remove Nth Node From End of List
3 *
4 * Given the head of a linked list, remove the n^th node from the end of the list and return its head.
5 *  
6 * Example 1:
7 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg" style="width: 542px; height: 222px;" />
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 *  
22 * Constraints:
23 * 
24 * The number of nodes in the list is sz.
25 * 1 <= sz <= 30
26 * 0 <= Node.val <= 100
27 * 1 <= n <= sz
28 * 
29 *  
30 * Follow up: Could you do this in one pass?
31 * 
32 */
33pub struct Solution {}
34#[allow(unused_imports)]
35use crate::util::linked_list::{ListNode, to_list};
36
37// problem: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
38// discuss: https://leetcode.com/problems/remove-nth-node-from-end-of-list/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42// Definition for singly-linked list.
43// #[derive(PartialEq, Eq, Clone, Debug)]
44// pub struct ListNode {
45//   pub val: i32,
46//   pub next: Option<Box<ListNode>>
47// }
48// 
49// impl ListNode {
50//   #[inline]
51//   fn new(val: i32) -> Self {
52//     ListNode {
53//       next: None,
54//       val
55//     }
56//   }
57// }
58impl Solution {
59    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
60        let mut step_cnt = 0;
61        let mut t = head.as_ref().unwrap();
62
63        while step_cnt < n {
64            if let Some(_) = t.next {
65                t = t.next.as_ref().unwrap();
66                step_cnt += 1;
67            } else {
68                return head.unwrap().next;
69            }
70        }
71        let mut cur = head.as_ref().unwrap();
72        let mut res = Some(Box::new(ListNode::new(cur.val)));
73        let mut res_cur = res.as_mut().unwrap();
74
75        while t.next.is_some() {
76            t = t.next.as_ref().unwrap();
77            cur = cur.next.as_ref().unwrap();
78            res_cur.next = Some(Box::new(ListNode::new(cur.val)));
79            res_cur = res_cur.next.as_mut().unwrap();
80        }
81
82        cur = cur.next.as_ref().unwrap();
83        // skip cur, and to the end
84        while cur.next.is_some() {
85            if let Some(ref n) = cur.next {
86                res_cur.next = Some(Box::new(ListNode::new(n.val)));
87            }
88            cur = cur.next.as_ref().unwrap();
89            res_cur = res_cur.next.as_mut().unwrap();
90        }
91
92        return res;
93    }
94}
95
96// submission codes end
97
98#[cfg(test)]
99mod tests {
100    use super::*;
101    use crate::linked;
102
103    #[test]
104    fn test_19() {
105        let x = linked!(1,2,3,4,5);
106        let y = Solution::remove_nth_from_end(x, 2);
107        ListNode::print(&y.unwrap());
108    }
109}
110