19. Remove Nth Node From End of List

Description of the Problem

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Follow up: Could you do this in one pass?

Solution (Does not fullfill the follow-up question)

Code (Java)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode currentNode = head;
        int len = 0;
        while(currentNode != null){
            len++;
            currentNode = currentNode.next;
        }

        ListNode sentinelHead = new ListNode(-1, head);
        currentNode = sentinelHead;
        while( len - n > 0 ){
            n++;
            currentNode = currentNode.next;
        }
        currentNode.next = currentNode.next.next;
        return sentinelHead.next;
    }
}

Code (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 n = n;
        // Reverse The List
        let mut curr = head;
        let mut prev = None;
        while let Some(mut node) = curr.take() {
            curr = node.next;
            node.next = prev;
            prev = Some(node);
        }

        // Reverse again and delete
        curr = prev;
        prev = None;
        while let Some(mut node) = curr.take() {
            n-=1;
            if (n != 0){
                curr = node.next;
                node.next = prev;
                prev = Some(node);
            }else{
                curr = node.next;
            }
        }

        return prev;
    }
}