DSA
Remove Nth Node From End of List
Covers: Naive, Better.
Practice here
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Naive approach#
First compute the total length of the list. The Nth node from the end is the (length - N + 1)th node from the start. Walk to the node just before it and relink curr->next = curr->next->next. This is simple but requires two full passes over the list.
Requires 2 traversals
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
int length(ListNode* head)
{
int count=0;
while(head){
head=head->next;
count++;
}
return count;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
int len = length(head);
ListNode* curr = head;
int nth = len - n + 1;
if(n==len)
return head->next;
for(int i=1;i<nth-1;i++){
curr=curr->next;
}
curr->next = curr->next->next;
return head;
}
};
Better Approach#
Use two pointers, fast and slow, both starting at the head. First advance fast by exactly N steps. If fast is now null the head itself must be removed (return head->next). Then move both pointers together until fast->next is null — at that point slow is at the node immediately before the target. Relink and return. The N-step head start ensures the gap between the pointers is exactly N, so slow lands at the right predecessor in a single pass.
Requires 1 traversal
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* fast=head;
ListNode* slow=head;
for(int i=0;i<n;i++)
fast=fast->next;
if(!fast)
return head->next;
while(fast->next)
{
slow=slow->next;
fast=fast->next;
}
slow->next=slow->next->next;
return head;
}
};