74. Remove Nth Node From End of List
🔗 LeetCode Problem: 19. Remove Nth Node From End of List
📊 Difficulty: Medium
🏷️ Topics: Linked List, Two Pointers
Problem Statement
Given the head of a linked list, remove the n-th node from the end of the list and return its head.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Visual:
Before: 1 -> 2 -> 3 -> 4 -> 5 -> null
↑
Remove this (2nd from end)
After: 1 -> 2 -> 3 -> 5 -> null
Example 2:
Input: head = [1], n = 1
Output: []
Explanation: Remove the only node, list becomes empty.
Example 3:
Input: head = [1,2], n = 1
Output: [1]
Explanation: Remove the last node (1st from end).
Constraints:
- The number of nodes in the list is sz.
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
Follow up: Could you do this in one pass?
🎨 Visual Understanding
The Problem Visualized
Example 1: Remove 2nd from end
List: 1 -> 2 -> 3 -> 4 -> 5 -> null
↑ ↑ ↑ ↑ ↑
5th 4th 3rd 2nd 1st from end
Remove 2nd from end (node 4):
1 -> 2 -> 3 -> 5 -> null
The Challenge: Finding nth from end
From start: Easy! Just count n steps
1 -> 2 -> 3 -> 4 -> 5
↑ ↑
Start 3rd from start
From end: Tricky!
Need to know total length OR use two pointers!
1 -> 2 -> 3 -> 4 -> 5
↑ ↑
3rd from end End
Two-pass approach:
Pass 1: Count total nodes = L
Pass 2: Move to (L - n)th node
Remove (L - n + 1)th node
Works but takes TWO passes!
One-pass approach:
Use TWO POINTERS with GAP! 🎯
🚨 CRITICAL INSIGHT - Maintain Fixed Gap!
The Key Pattern!
Use two pointers with a FIXED GAP of n+1:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow fast
Gap = n + 1 = 3 (for n = 2)
Why n+1 and not n?
We need slow to stop BEFORE the node to delete!
To delete node at position p:
We need pointer at position p-1
So we can do: slow.next = slow.next.next
Step 1: Move fast n+1 steps ahead
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow fast
Step 2: Move both together until fast reaches end
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow fast=null
Now slow is BEFORE the node to delete!
slow.next = slow.next.next (removes node 4)
Why Use Dummy Node?
Problem: What if we need to remove the HEAD?
Example: [1, 2, 3], n = 3 (remove 1st node from end = head)
Without dummy:
slow = head = 1
After moving: slow = 1 (still at head)
Can't access node BEFORE head to remove it! ✗
With dummy:
dummy -> 1 -> 2 -> 3 -> null
slow = dummy
After moving: slow = dummy (before head)
slow.next = slow.next.next removes head! ✓
Dummy node solves the "remove head" edge case!
Visual Trace - Step by Step
List: 1 -> 2 -> 3 -> 4 -> 5, n = 2
Step 1: Create dummy node
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow
fast
Step 2: Move fast n+1 = 3 steps ahead
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow fast
Gap between slow and fast = 3
Step 3: Move both until fast reaches null
Iteration 1:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow fast
Iteration 2:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow fast
Iteration 3:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow fast=null
Step 4: Remove node
slow.next = slow.next.next
3 -> 4 -> 5 becomes 3 -> 5
dummy -> 1 -> 2 -> 3 -> 5 -> null
Step 5: Return dummy.next (the actual head)
1 -> 2 -> 3 -> 5 -> null ✓
🎯 Approach 1: Two Pass (Count then Remove)
The Most Natural Thinking 💭
Core Logic:
Pass 1: Count total nodes = L
Pass 2: Move to (L - n)th position and remove
Implementation
/**
* Two-pass approach
* Time: O(L), Space: O(1)
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
// Pass 1: Count nodes
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
// Find position from start
int removeIndex = length - n; // 0-indexed position
// Edge case: remove head
if (removeIndex == 0) {
return head.next;
}
// Pass 2: Move to node before removal
current = head;
for (int i = 0; i < removeIndex - 1; i++) {
current = current.next;
}
// Remove node
current.next = current.next.next;
return head;
}
⏰ Time: O(L) - Two passes through list
💾 Space: O(1) - Only variables
✓ Works, but requires two passes!
🎯 Approach 2: Two Pointers with Gap (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
Use two pointers with fixed gap of n+1!
Step 1: Move fast n+1 steps ahead
Step 2: Move both until fast reaches null
Step 3: slow is now BEFORE node to delete
Step 4: slow.next = slow.next.next
One pass solution! ✓
The Strategy:
Two Pointers with Gap:
1. Create dummy node (handles remove head case)
2. Initialize slow = dummy, fast = dummy
3. Move fast n+1 steps ahead
4. Move both together until fast reaches null
5. Remove: slow.next = slow.next.next
6. Return dummy.next
Time: O(L) - Single pass
Space: O(1) - Two pointers + dummy
Implementation
/**
* Two Pointers with Gap - One Pass
* Time: O(L), Space: O(1)
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
// Create dummy node to handle edge cases
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
// Step 1: Move fast n+1 steps ahead
// This creates a gap of n+1 between slow and fast
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// Step 2: Move both pointers until fast reaches end
// Maintain the gap of n+1
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
// Step 3: slow is now at the node BEFORE the one to delete
// Remove the nth node from end
slow.next = slow.next.next;
// Return the actual head (not dummy)
return dummy.next;
}
⏰ Time: O(L) - Single pass through list
💾 Space: O(1) - Only two pointers + dummy node
🔍 Dry Run
Example 1: [1,2,3,4,5], n = 2
Goal: Remove 2nd from end (node 4)
Step 1: Create dummy
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow
fast
Step 2: Move fast n+1 = 3 steps ahead
i = 0: fast = 1
i = 1: fast = 2
i = 2: fast = 3
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow fast
Step 3: Move both until fast reaches null
Iteration 1:
slow = 1, fast = 4
Iteration 2:
slow = 2, fast = 5
Iteration 3:
slow = 3, fast = null
Final positions:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow fast=null
Step 4: Remove node
slow.next = slow.next.next
3.next = 4.next = 5
dummy -> 1 -> 2 -> 3 -> 5 -> null
Step 5: Return dummy.next
1 -> 2 -> 3 -> 5 -> null ✓
Example 2: [1], n = 1
Goal: Remove only node (becomes empty)
Step 1: Create dummy
dummy -> 1 -> null
slow
fast
Step 2: Move fast n+1 = 2 steps
i = 0: fast = 1
i = 1: fast = null
dummy -> 1 -> null
slow fast=null
Step 3: While loop
fast = null, loop doesn't execute
slow = dummy
Step 4: Remove node
slow.next = slow.next.next
dummy.next = 1.next = null
dummy -> null
Step 5: Return dummy.next
null (empty list) ✓
Example 3: [1,2], n = 2 (Remove head)
Goal: Remove 2nd from end = head
Step 1: Create dummy
dummy -> 1 -> 2 -> null
slow
fast
Step 2: Move fast n+1 = 3 steps
i = 0: fast = 1
i = 1: fast = 2
i = 2: fast = null
dummy -> 1 -> 2 -> null
slow fast=null
Step 3: While loop doesn't execute
slow = dummy
Step 4: Remove node
slow.next = slow.next.next
dummy.next = 1.next = 2
dummy -> 2 -> null
Step 5: Return dummy.next
2 -> null ✓
(Head successfully removed!)
🎯 Why This Works - Deep Dive
The Gap Strategy:
═══════════════════════════════════════════════════════════════
Key insight: Maintain fixed gap between pointers!
Gap = n + 1 (not n!)
Why n+1?
To delete node at position p from end:
We need pointer at position p+1 from end
Then: pointer.next = pointer.next.next
Example: Delete 2nd from end
Need pointer at 3rd from end
Gap = 2 + 1 = 3 ✓
Visual proof:
List: 1 -> 2 -> 3 -> 4 -> 5
To remove 4 (2nd from end):
Need to be at 3 (3rd from end)
Then: 3.next = 3.next.next = 5
Gap needed: 3 positions
n = 2, gap = n+1 = 3 ✓
The Dummy Node:
═══════════════════════════════════════════════════════════════
Why dummy node is CRITICAL:
Problem: Removing head
List: 1 -> 2 -> 3, n = 3
Without dummy:
slow starts at 1 (head)
After moving: slow = 1
Can't access node before 1 to remove it! ✗
With dummy:
dummy -> 1 -> 2 -> 3
slow starts at dummy
After moving: slow = dummy
slow.next = slow.next.next removes 1! ✓
Dummy provides a "before head" position!
The Moving Strategy:
═══════════════════════════════════════════════════════════════
Phase 1: Create gap
Move fast n+1 steps
slow stays at dummy
Gap = n+1 established ✓
Phase 2: Move together
Move both at same speed (1 step each)
Gap remains constant = n+1 ✓
When fast reaches null:
slow is n+1 positions from end
= (n+1) - 1 = n positions from end
= 1 position before node to delete ✓
Phase 3: Delete
slow.next = target node
slow.next.next = node after target
Connect: slow -> node after target
Skip target node ✓
Why Single Pass?
═══════════════════════════════════════════════════════════════
Traditional approach:
Pass 1: Count length = L
Pass 2: Move to L - n position
Total: 2 passes
Two pointer approach:
Setup + move together = 1 pass
Fast pointer travels entire list once:
Initial: n+1 steps
Then: L - (n+1) steps to reach null
Total: n+1 + (L-n-1) = L steps ✓
Slow pointer travels L - (n+1) steps
Combined: Single traversal! ✓
Time Complexity:
═══════════════════════════════════════════════════════════════
Fast pointer moves L positions total:
Time: O(L)
Slow pointer moves L - (n+1) positions:
Time: O(L - n) = O(L)
Overall: O(L) ✓
Space: O(1) - Only two pointers + dummy
Why Gap is n+1 (Mathematical Proof):
═══════════════════════════════════════════════════════════════
List length: L
Node to remove: nth from end
Position from start: L - n (0-indexed)
We need pointer at position: L - n - 1
(One before the node to delete)
When fast reaches null (position L):
slow at position: L - gap
We need: slow at L - n - 1
Therefore: L - gap = L - n - 1
gap = n + 1 ✓
Example verification:
L = 5, n = 2
Remove position from start: 5 - 2 = 3
Need slow at: 3 - 1 = 2
gap = n + 1 = 3
When fast at 5: slow at 5 - 3 = 2 ✓
Alternative: Without Dummy (More Complex)
/**
* Without dummy node (more edge cases)
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode slow = head;
ListNode fast = head;
// Move fast n steps ahead (not n+1)
for (int i = 0; i < n; i++) {
fast = fast.next;
}
// Special case: remove head
if (fast == null) {
return head.next;
}
// Move both until fast reaches last node
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
// Remove node
slow.next = slow.next.next;
return head;
}
// More edge cases to handle!
// Dummy node version is CLEANER ✓
⚠️ Common Mistakes to Avoid
Mistake 1: Gap of n instead of n+1
// ❌ WRONG - Gap of n
for (int i = 0; i < n; i++) {
fast = fast.next;
}
// slow ends AT node to delete, not BEFORE it!
// ✓ CORRECT - Gap of n+1
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// slow ends BEFORE node to delete ✓
Mistake 2: Not using dummy node
// ❌ WRONG - Complex edge cases
ListNode slow = head;
ListNode fast = head;
// Can't easily handle removing head!
// ✓ CORRECT - Dummy handles all cases
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
Mistake 3: Wrong loop condition
// ❌ WRONG - Off by one
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
// ✓ CORRECT - Move until fast is null
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
Mistake 4: Returning head instead of dummy.next
// ❌ WRONG - Returns old head (might be removed)
return head;
// ✓ CORRECT - Returns actual head
return dummy.next;
Mistake 5: Not initializing fast correctly
// ❌ WRONG - Fast starts at head.next
ListNode fast = head.next;
// ✓ CORRECT - Both start at dummy
ListNode slow = dummy;
ListNode fast = dummy;
🎯 Pattern Recognition
Problem Type: Remove Node from Linked List
Core Pattern: Two Pointers with Fixed Gap
When to Apply:
✓ Remove nth from end
✓ Need one-pass solution
✓ Can't count nodes first
✓ Access node before target
✓ Handle remove head case
Recognition Keywords:
- "nth from end"
- "remove node"
- "one pass" solution
- "end of list"
- Delete from linked list
Similar Problems:
- Delete N Nodes After M (LC 1474)
- Delete Middle Node (LC 2095)
- Swap Nodes (LC 1721) - kth from start and end
Key Components:
┌────────────────────────────────────────────┐
│ 1. Dummy node (handle edge cases) │
│ 2. Two pointers with gap n+1 │
│ 3. Move fast ahead first │
│ 4. Move both until fast reaches null │
│ 5. slow.next = slow.next.next │
└────────────────────────────────────────────┘
This is a CLASSIC interview problem!
🧠 Interview Strategy
Step 1: "Remove nth from end → Two pointers with gap"
Step 2: "Use dummy node for edge cases"
Step 3: "Gap of n+1, not n"
Step 4: "Move fast ahead, then both together"
Step 5: "One pass, O(1) space"
Key Points to Mention:
- Two pointers with fixed gap
- Gap = n+1 (to be BEFORE node to delete)
- Dummy node handles remove head
- Move fast n+1 steps first
- Then move both until fast is null
- slow ends before node to delete
- Remove: slow.next = slow.next.next
- Return dummy.next (actual head)
- Time: O(L), Space: O(1)
Why This Approach?
"I'll use two pointers with a fixed gap. First, I create a
dummy node to handle the edge case of removing the head. Then
I move the fast pointer n+1 steps ahead to establish a gap.
The gap is n+1, not n, because I need the slow pointer to stop
at the node BEFORE the one to delete. Then I move both pointers
together until fast reaches null. At this point, slow is
positioned right before the node to remove, so I can delete it
with slow.next = slow.next.next. This gives a one-pass solution."
Why Dummy Node?
"The dummy node is crucial for handling the case where we need
to remove the head. Without it, we'd have no way to access the
node before the head. The dummy provides a 'before head'
position that makes all cases uniform."
Why Gap is n+1?
"To delete a node, we need a pointer to the node before it.
If the target is nth from end, we need to be at (n+1)th from
end. The gap of n+1 ensures slow stops at the correct position."
Edge Cases to Mention:
✓ Remove head (first node)
✓ Remove tail (last node)
✓ Single node list
✓ Two node list
✓ n equals list length
📝 Quick Revision Notes
🎯 Core Concept:
Remove Nth From End: Use two pointers with gap n+1! Dummy node (handles remove head). Fast ahead n+1 steps, then both move until fast = null. Slow at node BEFORE target. Remove: slow.next = slow.next.next. Return dummy.next. One pass, O(L) time, O(1) space!
⚡ Quick Implementation:
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Test {
public ListNode removeNthFromEnd(ListNode head, int n) {
// key logic -
// 1. move fast ahead of slow by keeping gap of n+1
// 2. have dummy node - to handle edge case of a single node.
// why n+1? do a paper work for 1->2->3->4->5
// fast should be at null and slow should be just before the node that needs to be deleted
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
// Pre-move fast n + 1 steps ahead.
int i = 0;
while(i < n + 1 && fast != null) {
fast = fast.next;
i++;
}
// Now move both fast and slow together until fast reaches end.
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next; // do a jump
return dummy.next; // ignoring the dummy node 0.
}
private void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " -> ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Test t = new Test();
ListNode head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(3);
head1.next.next.next = new ListNode(4);
head1.next.next.next.next = new ListNode(5);
t.printList(t.removeNthFromEnd(head1, 2)); // remove middle
ListNode head2 = new ListNode(1); // single node
t.printList(t.removeNthFromEnd(head2, 1));
ListNode head3 = new ListNode(1); // remove head
head3.next = new ListNode(2);
head3.next.next = new ListNode(3);
t.printList(t.removeNthFromEnd(head3, 3));
ListNode head4 = new ListNode(1); // remove tail
head4.next = new ListNode(2);
head4.next.next = new ListNode(3);
t.printList(t.removeNthFromEnd(head4, 1));
ListNode head5 = new ListNode(1); // 2 nodes, remove first
head5.next = new ListNode(2);
t.printList(t.removeNthFromEnd(head5, 2));
ListNode head6 = new ListNode(1); // 2 nodes, remove second
head6.next = new ListNode(2);
t.printList(t.removeNthFromEnd(head6, 1));
}
}
🔑 Key Insights:
- Pattern: Two Pointers with Fixed Gap
- Dummy: Handles remove head case
- Gap: n+1 (not n!) - to be BEFORE target
- Phase 1: Move fast n+1 steps (create gap)
- Phase 2: Move both until fast = null
- Result: slow before target node
- Remove: slow.next = slow.next.next
- Return: dummy.next (actual head)
- Time: O(L), Space: O(1)
🎪 Memory Aid:
"Gap of n+1! Fast ahead, both move, slow before target!"
Think: "Dummy for head, gap to position before!" 🎯
💡 The Key Insight:
Why n+1 gap?
To delete node: Need pointer BEFORE it
nth from end → need (n+1)th from end
Gap = n+1 ensures slow at correct position!
⚠️ Critical Details:
1. Create dummy: new ListNode(0), dummy.next = head
2. Both start: slow = dummy, fast = dummy
3. Move fast: n+1 steps (loop i <= n, not i < n)
4. Move both: while (fast != null)
5. slow now: BEFORE node to delete
6. Remove: slow.next = slow.next.next
7. Return: dummy.next (NOT head!)
8. Why dummy? Handles remove head uniformly
🔥 The Gap Calculation:
List: 1 -> 2 -> 3 -> 4 -> 5, n = 2
Need to remove: 4 (2nd from end)
Need slow at: 3 (3rd from end, BEFORE 4)
Gap needed: 3 positions = n + 1 ✓
After gap created:
dummy -> 1 -> 2 -> 3 -> 4 -> 5
slow fast
After moving both:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow fast
Perfect! slow before 4 ✓
💡 Why Dummy is Critical:
Remove head case: [1, 2, 3], n = 3
Without dummy:
slow = 1 (head)
Can't access before head! ✗
With dummy:
dummy -> 1 -> 2 -> 3
slow = dummy
Can remove head via dummy.next! ✓
Dummy creates "before head" position!
🎯 The Algorithm Flow:
1. Setup: dummy -> original list
2. Gap: fast moves n+1 ahead
3. Scan: both move until fast = null
4. Delete: slow.next = slow.next.next
5. Return: dummy.next
Visual:
Setup: D -> 1 -> 2 -> 3 -> 4 -> 5
S
F
Gap: D -> 1 -> 2 -> 3 -> 4 -> 5
S F
Scan: D -> 1 -> 2 -> 3 -> 4 -> 5 -> null
S F
Delete: D -> 1 -> 2 -> 3 -----> 5 -> null
S
Return: 1 -> 2 -> 3 -> 5 -> null ✓
🧪 Edge Cases
Case 1: Remove only node
Input: head = [1], n = 1
Output: []
(List becomes empty)
Case 2: Remove head
Input: head = [1,2,3], n = 3
Output: [2,3]
(Remove first node)
Case 3: Remove tail
Input: head = [1,2,3], n = 1
Output: [1,2]
(Remove last node)
Case 4: Two nodes, remove first
Input: head = [1,2], n = 2
Output: [2]
Case 5: Two nodes, remove second
Input: head = [1,2], n = 1
Output: [1]
Case 6: Remove middle
Input: head = [1,2,3,4,5], n = 3
Output: [1,2,4,5]
(Remove 3rd from end = node 3)
All handled correctly! ✓
Related Patterns
- Delete Middle Node (LC 2095) - Similar deletion
- Swap Nodes in Pairs (LC 24) - Node manipulation
- Reverse Nodes in k-Group (LC 25) - Advanced manipulation
Happy practicing! 🎯
Note: This is a CLASSIC interview problem that tests your understanding of two pointers AND linked list manipulation! The dummy node technique is essential for clean code! 🎯