Posted on Jun 20, 2020

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

#computerscience #webdev #career #javascript

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; };