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) {
    if(n == 0) return head;
    let dummy = head;
    let len = 0;
    while(dummy.next != null){
        len++;
        dummy = dummy.next;
    }
    let nth = len-n+1;
    let prev = null;
    dummy = head;
    while(nth-- !=0){
        prev = dummy;
        dummy = dummy.next;
    }
    if(prev !=null)
    {   prev.next = dummy.next;
        dummy.next = null;
    }else{
        return head.next;
    }
    return head;
};

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{
        return head.next;
    }

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) {
    let fast = head;
    let slow = head;
    while(n-- > 0){
          fast = fast.next;
    }
    let prev = null;
    while(fast != null){
        fast = fast.next;
        prev = slow;
        slow = slow.next;
    }
    if(prev == null){
        return head.next;
    }
    prev.next = slow.next;
    slow.next = null;
    return head;

};

That's it ! Hope you liked my explanation.

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/removeNthNodefromEnd.js