Logo

Kode$word

Remove Nth Node From End – The Smart Way to Solve in One Pass (LeetCode 19)
Remove Nth Node From End – The Smart Way to Solve in One Pass (LeetCode 19)

Remove Nth Node From End – The Smart Way to Solve in One Pass (LeetCode 19)

Stop Counting Twice! Learn the Two-Pointer Trick to Remove Nodes Efficiently from the End of a Linked List

4 views
0
0
Linked ListTwo PointersFast & Slow PointerOne Pass AlgorithmLeetCodeMedium
Github icon

🚀 Try the Problem

Practice here:

https://leetcode.com/problems/remove-nth-node-from-end-of-list/


🤔 Let’s Think Differently…

Imagine this list:

1 → 2 → 3 → 4 → 5

You are asked:

👉 Remove the 2nd node from the end

So counting from end:

5 (1st), 4 (2nd) ❌ remove this

Final list:

1 → 2 → 3 → 5


🧠 Problem in Simple Words

You are given:

  1. Head of a linked list
  2. A number n

👉 Remove the nth node from the end

👉 Return the updated list


📦 Constraints

1 <= number of nodes <= 30
0 <= Node.val <= 100
1 <= n <= size of list


🧩 First Thought (Counting Method)

💡 Idea

  1. Count total nodes
  2. Find position from start:
position = total - n
  1. Traverse again and remove that node


✅ Code (Counting Approach)

class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {

if(head == null) return head;

// Step 1: Count nodes
int co = 0;
ListNode tempHead = head;

while(tempHead != null){
co++;
tempHead = tempHead.next;
}

// Step 2: If removing head
if(co == n) return head.next;

// Step 3: Find node before target
int k = co - n;
int con = 1;
ListNode temp = head;

while(con < k){
temp = temp.next;
con++;
}

// Step 4: Remove node
temp.next = temp.next.next;

return head;
}
}


⏱️ Complexity

Time Complexity

O(n) + O(n) = O(n)

(two traversals)

Space Complexity

O(1)


⚠️ Limitation of This Approach

👉 It requires two passes

But the problem asks:

Can you solve it in one pass?


🚀 Optimal Approach: Two Pointer Technique (One Pass)

Now comes the interesting part 🔥

🧠 Core Idea

We use two pointers:

fast pointer
slow pointer


🎯 Trick

👉 Move fast pointer n steps ahead

Then move both pointers together until:

fast reaches end

At that moment:

👉 slow will be at the node before the one to remove


📌 Why This Works

Because the gap between fast and slow is always n nodes

So when fast reaches end:

👉 slow is exactly where we need it


🔥 Step-by-Step Visualization

List:

1 → 2 → 3 → 4 → 5

n = 2

Step 1: Move fast 2 steps

fast → 3
slow → 1

Step 2: Move both together

fast → 4, slow → 2
fast → 5, slow → 3
fast → null, slow → 4

👉 Now slow is at node before target


🧼 Clean and Safe Approach (Using Dummy Node)

Using dummy node avoids edge cases like removing head.

💻 Code (Optimal One Pass Solution)

class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {

// Dummy node to handle edge cases
ListNode dummy = new ListNode(0, head);

ListNode fast = dummy;
ListNode slow = dummy;

// Move fast pointer n steps ahead
for(int i = 0; i < n; i++){
fast = fast.next;
}

// Move both pointers
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}

// Remove nth node
slow.next = slow.next.next;

return dummy.next;
}
}

⏱️ Complexity

Time Complexity

O(n)

(single pass)

Space Complexity

O(1)


⚖️ Comparing Approaches

ApproachPassesTimeSpaceDifficulty
Counting2O(n)O(1)Easy
Two Pointer1O(n)O(1)Optimal


❌ Common Mistakes

  1. Forgetting to handle removing head node
  2. Not using dummy node
  3. Off-by-one errors in pointer movement
  4. Moving fast incorrectly


🔥 Interview Insight

This problem is a classic example of:

Fast & Slow Pointer Technique

Used in many problems like:

  1. Cycle Detection
  2. Middle of Linked List
  3. Palindrome Linked List


🧠 Final Thought

At first, counting feels natural…

But once you learn this trick:

"Create a gap and move together"

👉 You unlock a powerful pattern.


🚀 Conclusion

The Remove Nth Node From End problem is not just about deletion…

It teaches:

  1. Efficient traversal
  2. Pointer coordination
  3. One-pass optimization

👉 Tip: Whenever you see “from end”, think:

"Can I use two pointers with a gap?"

That’s your shortcut to solving these problems like a pro 🚀

Related Articles

Reverse Linked List (LeetCode 206) – The One Trick That Changes Everything

Reverse Linked List (LeetCode 206) – The One Trick That Changes Everything

From Confusion to Clarity: Master Linked List Reversal with Intuition, Visualization, and Clean Logic

Read Article
LeetCode 203: Remove Linked List Elements – Step-by-Step Guide for Beginners

LeetCode 203: Remove Linked List Elements – Step-by-Step Guide for Beginners

Learn How to Remove Nodes from a Linked List Using Iteration, Edge Case Handling, and Dummy Node Technique (With Clear Intuition)

Read Article
Intersection of Two Linked Lists – The Smart Trick Most People Miss (LeetCode 160)

Intersection of Two Linked Lists – The Smart Trick Most People Miss (LeetCode 160)

Understand Why Two Pointers Meet Exactly at the Intersection Without Extra Space (Simple + Powerful Intuition)

Read Article
LeetCode 328: Odd Even Linked List – Clean and Easy Explanation with Multiple Approaches

LeetCode 328: Odd Even Linked List – Clean and Easy Explanation with Multiple Approaches

Learn How to Rearrange a Linked List by Odd and Even Positions Using Optimal O(1) Space Approach

Read Article

Ai Assistant Kas