# Remove Nth Node From End Of List
Difficulty: Medium Pattern: Linked List Language: cpp
LeetCode: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
## Intuition
In this problem we need to remove the nth node from the end of the linked list. A simple way would be to first calculate the length of the list and then find the node to remove, but that would require two passes.
Instead, we can solve this in one traversal using the two-pointer technique. We use two pointers called fast and slow. First we move the fast pointer n steps ahead to create a gap between the two pointers. Then we move both pointers forward one step at a time. When the fast pointer reaches the end of the list, the slow pointer will be just before the node that needs to be deleted.
To make deletion easier when the first node has to be removed, we use a dummy node before the head.
## Approach
Create a dummy node and connect it to the head of the list. Initialize two pointers fast and slow starting from the dummy node. Move the fast pointer n steps ahead to create a gap. Move both fast and slow forward together until fast reaches the last node. Now slow will be positioned just before the node we want to delete. Remove the node by updating: slow->next = slow->next->next. Return dummy->next as the new head.
## Example Walkthrough
head = [1,2,3,4,5], n = 2
Step 1: Move fast pointer n steps ahead → slow → 1, fast → 3
Step 2: Move both together → slow → 3, fast → 5
Step 3: Remove the node → slow->next = slow->next->next
Final list: 1 → 2 → 3 → 5
## Time Complexity O(n)
## Space Complexity O(1)
## Code
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
ListNode* fast = dummy;
ListNode* slow = dummy;
while (n--) {
fast = fast->next;
}
while (fast->next) {
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
return dummy->next;
}
};
LeetSync | Synced from browser extension
