Remove Nth Node From Endof List Algorithm
The Remove Nth Node From End of List Algorithm is a widely used technique in computer programming, specifically for manipulating linked lists. It is designed to efficiently remove the nth node from the end of a singly linked list, given only the head of the list. The algorithm operates in a single pass through the list, making it highly efficient in terms of both time and space complexity. This is especially important in situations where the linked list is very long, as it prevents the need for multiple traversals of the list or the use of additional data structures.
To execute the Remove Nth Node From End of List Algorithm, two pointers are employed. The first pointer, often called the "first" or "lead" pointer, advances n nodes ahead of the second pointer, also known as the "second" or "lag" pointer. Both pointers then traverse the list together, with the first pointer maintaining its n-node lead. When the first pointer reaches the end of the list, the second pointer will be positioned at the (n-1)th node from the end. At this point, the second pointer can easily remove the nth node by updating the next pointer of the (n-1)th node to bypass the nth node. This ensures that the algorithm operates in O(n) time complexity, as it only requires a single pass through the list.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
ListNode prevHead(0);
prevHead.next = head;
ListNode *prev = &prevHead;
ListNode *slow = head;
ListNode *fast = head;
for (int i = 0; i < n; i++)
fast = fast->next;
while (fast != NULL) {
prev = prev->next;
slow = slow->next;
fast = fast->next;
}
prev->next = slow->next;
delete slow;
return prevHead.next;
}
};
