DEV Community

Akhil
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:
Alt Text

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;
};
Enter fullscreen mode Exit fullscreen mode

An edge case: if for eg:

List : [1,2]
n : 2
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

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 : Alt Text

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;

};
Enter fullscreen mode Exit fullscreen mode

That's it ! Hope you liked my explanation.

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

Oldest comments (0)