# Question

Formatted question description: https://leetcode.ca/all/19.html

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 = , n = 1
Output: []


Example 3:

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


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?

# Algorithm

The problem requires a single traversal to solve the problem, so you have to think of some more clever ways. For example, the first thing to consider is how to find the Nth node from the bottom. Since only one traversal is allowed, a complete traversal cannot be used to count the number of elements in the linked list. Instead, it should be removed after traversing to the corresponding position.

So you need to use two pointers to help solve the problem, pre and cur pointers. First, the cur pointer moves forward by N steps. If cur points to empty at this time, indicating that N is the length of the linked list, the first element that needs to be removed is the first element. Then return head->next at this time. If cur exists, continue to Go down, at this time the pre pointer also follows, until cur is the last element and stop, at this time pre points to the previous element of the element to be removed, and then modify the pointer to skip the element to be removed

# Code

• 
public class Remove_Nth_Node_From_End_of_List {

public static void main(String[] args) {

}

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {

ListNode nBehindPrev = new ListNode(0);
nBehindPrev.next = nBehind;

// nBehind starts moving after n steps of current
//    Given linked list: 1->2->3->4->5, and n = 2.
int count = 0;
while (current != null) {
if (count >= n) {
nBehindPrev = nBehindPrev.next; // note order
nBehind = nBehind.next;
}

current = current.next;
count++;
}

// cut
nBehindPrev.next = nBehind.next;
nBehind.next = null; // maybe not required, both pointing to nBehind.next

}
}

public class Solution_2Scan {

// actually it's scanning twice
public ListNode removeNthFromEnd_refactor(ListNode head, int n) {
}

// move first node to desired position first, avoid flag and count etc.
int count = 0;
while(count < n) {
count++;
current = current.next;
}

ListNode dummy = new ListNode(0);

ListNode toDeletePrev = dummy;

while(current != null) {

current = current.next;

toDelete = toDelete.next;
toDeletePrev = toDeletePrev.next;

}

// remove the one
toDeletePrev.next = toDelete.next;

return dummy.next;
}

public ListNode removeNthFromEnd(ListNode head, int n) {
}

ListNode dummy = new ListNode(0);

// @note: key is the initialization. at first I set null,
// but if null and input only one node, cannot enter while loop and below 2 variables stay null
ListNode toDeletePrev = dummy;

boolean flag = false;
int count = 0;
ListNode current = dummy;
while(current != null) {

if(count > n && !flag) {
flag = true;
toDeletePrev = dummy;
}

current = current.next;

if(flag) {
toDelete = toDelete.next;
toDeletePrev = toDeletePrev.next;
}

count++;
}

// remove the one
toDeletePrev.next = toDelete.next;

return dummy.next;
}
}

}

############

/**
* 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 dummy = new ListNode(0, head);
ListNode fast = dummy, slow = dummy;
while (n-- > 0) {
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}

• // OJ: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
// Time: O(N)
// Space: O(1)
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
while (n--) q = q->next;
while (q->next) {
p = p->next;
q = q->next;
}
p->next = p->next->next;
}
};

• # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
fast = slow = dummy
for _ in range(n):
fast = fast.next
while fast.next:
slow, fast = slow.next, fast.next
slow.next = slow.next.next
return dummy.next

############

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:type n: int
:rtype: ListNode
"""
dummy = ListNode(-1)
fast = slow = dummy

while n and fast:
fast = fast.next
n -= 1

while fast.next and slow.next:
fast = fast.next
slow = slow.next

slow.next = slow.next.next
return dummy.next


• /**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
fast, slow := dummy, dummy
for ; n > 0; n-- {
fast = fast.Next
}
for fast.Next != nil {
slow, fast = slow.Next, fast.Next
}
slow.Next = slow.Next.Next
return dummy.Next
}

• /**
* class ListNode {
*     val: number
*     next: ListNode | null
*     constructor(val?: number, next?: ListNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.next = (next===undefined ? null : next)
*     }
* }
*/

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy = new ListNode(0, head);
let fast = dummy;
let slow = dummy;
while (n--) {
fast = fast.next;
}
while (fast.next) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}


• /**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function (head, n) {
const dummy = new ListNode(0, head);
let fast = dummy,
slow = dummy;
while (n--) {
fast = fast.next;
}
while (fast.next) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
};


• # Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {Integer} n
# @return {ListNode}
fast = slow = dummy
while n > 0
fast = fast.next
n -= 1
end
while fast.next
slow = slow.next
fast = fast.next
end
slow.next = slow.next.next
return dummy.next
end

• // 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 slow = &mut dummy;
let mut fast = &slow.clone();
for _ in 0..=n {
fast = &fast.as_ref().unwrap().next;
}
while fast.is_some() {
fast = &fast.as_ref().unwrap().next;
slow = &mut slow.as_mut().unwrap().next;
}
slow.as_mut().unwrap().next = slow.as_mut().unwrap().next.as_mut().unwrap().next.take();
dummy.unwrap().next
}
}