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.
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.
Top comments (0)