Approach Summary
Two pointers: advance fast by n+1 steps, then move both until fast is null. Slow is one before the target; relink to skip it.
Practice Mode
3 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Two Pointers with Dummy Node in One Pass (Optimal) | O(L) | O(1) | Space two pointers by n nodes using a dummy head; when fast reaches end, slow is right before target. |
| 2 Approach 2: Two-Pass Node Counting (Baseline) | O(n) | O(1) | First pass computes list length L; second pass advances L - n steps to delete target node. |
| 3 Approach 2: Two-Pass Node Counting (Baseline) | O(n) | O(1) | First pass computes list length L; second pass advances L - n steps to delete target node. |
Step 1: Baseline
Approach 1: Two Pointers with Dummy Node in One Pass (Optimal)
Time: O(L)
Space: O(1)
Create a dummy node pointing to head to handle head-removal cleanly. Move fast pointer n + 1 steps ahead. Then advance slow and fast simultaneously until fast reaches null. slow.next will be pointing precisely to the node to remove, so set slow.next = slow.next.next.
Approach 1: Two Pointers with Dummy Node in One Pass (Optimal) Implementation
Approach 1: Two Pointers with Dummy Node in One Pass (Optimal)
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode ptr1 = dummy, ptr2 = dummy;
for (int i = 0; i <= n; i++) ptr1 = ptr1.next;
while (ptr1 != null) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
ptr2.next = ptr2.next.next;
return dummy.next;
}
}class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* ptr1 = dummy;
ListNode* ptr2 = dummy;
for (int i = 0; i <= n; i++) ptr1 = ptr1->next;
while (ptr1 != NULL) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
ListNode* toDelete = ptr2->next;
ptr2->next = ptr2->next->next;
delete toDelete;
return dummy->next;
}
};class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n + 1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.nextfunction removeNthFromEnd(head, n) {
const dummy = new ListNode(0, head);
let fast = dummy, slow = dummy;
for (let i = 0; i <= n; i++) fast = fast.next;
while (fast !== null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
} Step 2
Approach 2: Two-Pass Node Counting (Baseline)
Time: O(n)
Space: O(1)
Traverse list once to determine total node count L. Create a dummy node pointing to head. Traverse L - n nodes from dummy to reach the node immediately preceding the target node, then update curr.next = curr.next.next.
Approach 2: Two-Pass Node Counting (Baseline) Implementation
Approach 2: Two-Pass Node Counting (Baseline)
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
int length = 0;
ListNode curr = head;
while (curr != null) { length++; curr = curr.next; }
curr = dummy;
for (int i = 0; i < length - n; i++) curr = curr.next;
curr.next = curr.next.next;
return dummy.next;
}
}class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
int len = 0;
ListNode* curr = head;
while (curr) { len++; curr = curr->next; }
curr = dummy;
for (int i = 0; i < len - n; i++) curr = curr->next;
curr->next = curr->next->next;
return dummy->next;
}
};class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
length = 0
curr = head
while curr:
length += 1
curr = curr.next
curr = dummy
for _ in range(length - n):
curr = curr.next
curr.next = curr.next.next
return dummy.nextfunction removeNthFromEnd(head, n) {
const dummy = new ListNode(0, head);
let len = 0, curr = head;
while (curr) { len++; curr = curr.next; }
curr = dummy;
for (let i = 0; i < len - n; i++) curr = curr.next;
curr.next = curr.next.next;
return dummy.next;
} Step 2: Most Optimized
Approach 2: Two-Pass Node Counting (Baseline)
Time: O(n)
Space: O(1)
Traverse list once to determine total node count L. Create a dummy node pointing to head. Traverse L - n nodes from dummy to reach the node immediately preceding the target node, then update curr.next = curr.next.next.
Approach 2: Two-Pass Node Counting (Baseline) Implementation
Approach 2: Two-Pass Node Counting (Baseline)
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
int length = 0;
ListNode curr = head;
while (curr != null) { length++; curr = curr.next; }
curr = dummy;
for (int i = 0; i < length - n; i++) curr = curr.next;
curr.next = curr.next.next;
return dummy.next;
}
}class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
int len = 0;
ListNode* curr = head;
while (curr) { len++; curr = curr->next; }
curr = dummy;
for (int i = 0; i < len - n; i++) curr = curr->next;
curr->next = curr->next->next;
return dummy->next;
}
};class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
length = 0
curr = head
while curr:
length += 1
curr = curr.next
curr = dummy
for _ in range(length - n):
curr = curr.next
curr.next = curr.next.next
return dummy.nextfunction removeNthFromEnd(head, n) {
const dummy = new ListNode(0, head);
let len = 0, curr = head;
while (curr) { len++; curr = curr.next; }
curr = dummy;
for (let i = 0; i < len - n; i++) curr = curr.next;
curr.next = curr.next.next;
return dummy.next;
}Edge Cases to Watch
- Removing the head node (n equals the length of list; handled cleanly by dummy node)
- Single node list with n = 1 (returns null)
- Removing the last node (n = 1 on multi-node list; tail pointer adjusted to null)
Algorithmic Pattern
View Pattern Guide →
Master the Linked List Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Linked List pattern.
Framework: Linked List • Interview Prep: Tested at FAANG •
Explore all Linked List problems & invariants →
How to Recognize This Pattern
- "Remove nth from end in one pass"
- Offset two pointers by n to land at the right node
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
Linked List Two Pointers
Frequently Asked Questions
What is the optimal time and space complexity for Remove Nth Node From End of List?
The optimal solution for Remove Nth Node From End of List achieves O(n) runtime complexity and requires O(1) auxiliary space. Time complexity is O(L) where L is the number of nodes in the linked list because we perform a single linear traversal. Space complexity is O(1) auxiliary space as we only use two pointer references and a dummy node.
How do I identify that Remove Nth Node From End of List requires the Linked List pattern?
In technical interviews, look for key problem signals: "Remove nth from end in one pass"; Offset two pointers by n to land at the right node. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Linked List strategy.
What critical edge cases must be handled in Remove Nth Node From End of List?
Essential edge cases to verify include: Removing the head node (n equals the length of list; handled cleanly by dummy node); Single node list with n = 1 (returns null); Removing the last node (n = 1 on multi-node list; tail pointer adjusted to null). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Remove Nth Node From End of List?
Remove Nth Node From End of List is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Microsoft, Google, Apple.