## DEV Community 👩‍💻👨‍💻 is a community of 963,673 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Akhil

Posted on

# Remove Nth node from the end of a Linked List. Solving a Paypal interview question.

Question: Given a linked list, remove the n-th node from the end of the linked list and return its head.

eg if we're given a linked and asked to remove the 2nd node from the end:

Give it a try and comeback.

## Brute Force

A naive approach might be :
1 > Calculate the total length for the linked list.
2 > Determine the count of the node which is going to be nth from the end.
3 > Parse through the linked list and delete the node by setting it's previous node's next to current node's next.

Code :

``````var removeNthFromEnd = function(head, n) {
let len = 0;
while(dummy.next != null){
len++;
dummy = dummy.next;
}
let nth = len-n+1;
let prev = null;
while(nth-- !=0){
prev = dummy;
dummy = dummy.next;
}
if(prev !=null)
{   prev.next = dummy.next;
dummy.next = null;
}else{
}
};
``````

An edge case: if for eg:

``````List : [1,2]
n : 2
``````

In this case, 2 - 2 = 0, so the head must be removed, which means prev will be null. So the following case :

``````if(prev !=null)
{   prev.next = dummy.next;
dummy.next = null;
}else{
}
``````

But here we parsed the linked list twice, can we do better?

To solve this efficiently, we use concept of two pointers. The idea is really simple and intuitive.

Algorithm :
Step 1> Create two pointers slow and fast,
Step 2> first move the fast pointer to the nth node.
Step 3> now move the fast (at nth) and slow (at head) pointers one node at a time.
Step 4> when the fast pointer reaches the end, slow pointer is at the nth node.

Animation :

``````var removeNthFromEnd = function(head, n) {
while(n-- > 0){
fast = fast.next;
}
let prev = null;
while(fast != null){
fast = fast.next;
prev = slow;
slow = slow.next;
}
if(prev == null){
}
prev.next = slow.next;
slow.next = null;