Counting from the end of a singly linked list is awkward — you can only walk forward, and you don’t know the length until you’ve already passed the node you wanted. The clean fix is a fixed gap between two pointers, a staple of the linked list pattern toolkit. Get the gap right and the whole thing collapses to one pass.
The problem
Given the head of a singly linked list and a number n, delete the node that sits n positions from the tail and return the new head. (Full statement on LeetCode.)
So for 1 -> 2 -> 3 -> 4 -> 5 with n = 2, you drop the 4 and get 1 -> 2 -> 3 -> 5. The edge that bites people: n can point at the head itself, like removing the only node in a one-element list.
Intuition: freeze a gap of n between two pointers
The obvious plan is two passes — measure the length L, then walk L - n steps to reach the target. That works, but the length is really just a detour. What you actually need is to stop exactly n nodes before the end.
Here’s the trick. Send one pointer n steps ahead, then move both at the same speed. The lead pointer and the trailing pointer stay a constant n apart the whole way. When the lead falls off the end of the list, the trailing pointer is sitting n nodes back from the tail — which is precisely the node you want to unlink.
One more detail makes deletion clean. In a singly linked list you delete a node by rewiring its predecessor, so you don’t want to land on the target — you want to land on the node just before it. That means the trailing pointer should stop one short, so you widen the initial gap to n + 1 and start both pointers at a dummy node glued in front of the head. The dummy also erases the special case where the head itself gets removed: its predecessor is now a real node, not null.
Solution
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// Dummy sits before head so the "delete the head" case needs no special handling.
ListNode dummy = new ListNode(0, head);
ListNode lead = dummy;
ListNode trail = dummy;
// Open a gap of n+1 so trail lands on the node BEFORE the target.
for (int i = 0; i <= n; i++) {
lead = lead.next;
}
// Advance in lockstep; the gap is preserved until lead runs off the end.
while (lead != null) {
lead = lead.next;
trail = trail.next;
}
// trail.next is the node to remove — skip over it.
trail.next = trail.next.next;
return dummy.next;
}
}The i <= n loop runs n + 1 times, which is the whole reason trail ends up one node short of the target instead of on it. Returning dummy.next rather than head matters: if the original head was the node removed, head still references that now-unlinked node, while dummy.next holds the actual new head of the list.
Complexity
| Time | Space | |
|---|---|---|
| Two pointers, one pass |
L is the list length. The lead pointer touches each node once and the trailing pointer follows, so it’s a single linear sweep with a couple of pointers of extra space — the two-pass length-then-delete version has the same big-O but walks the list twice.
In an interview
Lead with the follow-up before they ask it: “I can do this in one pass by keeping two pointers n apart.” Then say why the dummy node earns its place — it turns “remove the head” from a special case into the normal case, and interviewers love hearing that you spotted the empty-result edge ([1], n = 1) before writing it. The classic off-by-one trap is advancing the lead by n instead of n + 1; if you land on the target you can’t rewire its predecessor in a singly linked list. Walk one tiny example out loud to prove the gap lands where you claim.
This fixed-gap idea is the same two-pointer instinct behind Linked List Cycle, where the pointers move at different speeds instead of a fixed distance, and it pairs naturally with Reverse Linked List once you’re comfortable rewiring next pointers. The pattern hub collects the rest.
