In our previous chapters, we mastered moving forward through a Linked List. But what happens when a problem asks you to count from the back?
Since a Singly Linked List is a one-way street, you can’t just start at the tail and move backward. You have two choices:
-
Traverse once to count the length, then traverse again to find the node. (Slow)
-
Use the “Gap” logic to find it in one single trip. (Pro approach)
The Intuition: The “Fixed Gap” Strategy
Imagine you and a friend are running a race. If your friend starts running and gets a 10-meter head start, and then you both run at the exact same speed, the distance between you will always remain 10 meters.
When your friend hits the finish line, you will be exactly 10 meters behind them. This is exactly how we find the Nth node from the end!
-
The Lead: Move the
Fastpointer N steps ahead. -
The Sync: Now, start the
Slowpointer from the beginning and move both at the same speed. -
The Target: When
Fastreaches the end (None),Slowwill be standing exactly on the Nth node from the last.
Python Code Implementation
This approach is clean, efficient, and shows a deep understanding of pointer manipulation.
def getNthFromLast(head, n):
slow = fast = head
# Step 1: Give the 'fast' pointer an N-step head start
for i in range(n):
if fast is None:
print("List is shorter than N!")
return None
fast = fast.next
# Step 2: Move both pointers until 'fast' reaches the end
while fast is not None:
slow = slow.next
fast = fast.next
# Now slow is pointing to the Nth node from the end
return slow.data
Step-by-Step Dry Run
Let’s find the 3rd node from the end (N=3) in this list:
[10] → [20] → [30] → [40] → [50] → [60]
-
Initial: Both
SlowandFastare at10. -
The Head Start: Move
Fast3 steps.Fastis now at40. -
The Race:
-
Move both:
Slowis at20,Fastis at50. -
Move both:
Slowis at30,Fastis at60. -
Move both:
Slowis at40,Fastis atNone.
-
-
Result:
Fasthit the end!Slowis resting at 40, which is exactly the 3rd node from the end.
Let’s understand with a tabular dry run also. A tabular dry run is one of the best ways to understand how pointers move in memory. It helps you visualize exactly what is happening inside the while loop at every step.
Let’s take a Linked List with 5 nodes and find the 2nd node from the end (N=2).
Linked List: 10 -> 20 -> 30 -> 40 -> 50 -> NULL
Initial State: slow and fast both point to 10.
Phase 1: Giving the fast pointer a head start (N=2)
| Step | slow position | fast position | Action |
| Initial | 10 | 10 | Start pointers at Head |
| Move 1 | 10 | 20 | fast moves 1st step |
| Move 2 | 10 | 30 | fast moves 2nd step (Gap of 2 created) |
Phase 2: Moving both pointers until fast hits the end
Now, both slow and fast move one step at a time. Watch how the gap of 2 remains constant.
| Iteration | slow moves to | fast moves to | fast.next status |
| Start | 10 | 30 | fast.next is 40 (Not NULL) |
| 1 | 20 | 40 | fast.next is 50 (Not NULL) |
| 2 | 30 | 50 | fast.next is NULL (STOP!) |
Final Result: The fast pointer has reached the last node. The slow pointer is now at 30. Since we were looking for the 2nd node from the end (N=2), the target is the node immediately after slow (which is 40).
Why this is a “One-Pass” Miracle
If you look at the table, you’ll notice:
-
We never had to count how many nodes were in the list.
-
We reached the answer as soon as the
fastpointer “smelled” the end of the list. -
Memory Usage: We only used two integer pointers (
slowandfast), making it very efficient for large datasets.
Key Takeaways for Students
-
Time Complexity: O(n). We only visit each node once.
-
Space Complexity: O(1). We aren’t creating new lists; we are just using two variables (
slowandfast). -
Logical Thinking: This problem teaches you how to use “relative distance” to solve positioning problems without needing to know the “absolute” size of your data.
Get the Full Source Code
I have uploaded the complete practice script to GitHub. It includes a helper function to create a linked list from an array so you can test it with different values of N.
👉 [Access the Practice Code on GitHub]
Frequently Asked Questions (FAQs)
1. What if N is 1?
If N=1, the fast pointer moves 1 step ahead. By the time it hits the end, slow will be at the very last node.
2. Can I use this to remove the node too?
Yes! To remove the node, you just need to stop the slow pointer one step before the target node so you can change the .next pointer.
3. Is there any other way?
You could use recursion, but that uses extra memory (stack space). The two-pointer method is the most memory-efficient way to solve this.
🎯 Build a Real Project (Don’t Stop at Theory!)
If you really want to master Linked Lists, don’t just solve problems — build something real.
👉 I’ve created a complete DSA Project – Expense Tracker using only:
- Singly Linked List
- Basic operations (insert, delete, reverse, traversal)
🔗 [Click here to explore the full project]
This will help you:
- Understand real-world use cases
- Strengthen DSA concepts
- Prepare for interviews + projects
