Remove Nth Node From End — One-Pass Two Pointers
Advance a front pointer n steps ahead so that when it hits null, the trailing pointer sits right before the node to remove.
Problem Statement
Delete the n-th node from the end of a singly linked list in one pass.
Why This Problem Matters
- Reinforces dummy-head patterns for simplifying edge cases like removing the first node.
- Highlights how pointer offsets solve "from the end" problems without length precomputation.
- Often used to introduce multi-pass vs single-pass trade-offs.
Thought Process
Consider the two-pass solution
Counting nodes first works but does not meet the follow-up asking for one pass.
Offset two pointers by n steps
When the fast pointer reaches the list end, the slow pointer sits just before the target.
Use a dummy head
Dummy nodes keep head deletion simple and eliminate special cases.
Step-by-Step Reasoning
- Create a dummy pointing to head; set slow and fast to dummy.
- Advance fast by n + 1 steps so the gap between fast and slow is exactly n nodes.
- Move slow and fast together until fast hits null.
- Skip slow.next to remove the target node and return dummy.next.
Dry Run
List = 1→2→3→4→5, n = 2
fast advances to node 4 before sync walk; slow stops at node 3 and removes 4.
List = 1→2, n = 2
fast runs out after offset, slow stays at dummy and removes head node 1.
Complexity Analysis
Time
O(n)
Space
O(1)
Why
Each pointer traverses at most n nodes using constant auxiliary storage.
Annotated Solution
public class RemoveNthNodeFromEndOfList {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode slow = dummy;
ListNode fast = dummy;
for (int i = 0; i < n + 1; i += 1) {
fast = fast.next;
}
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
public static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
}Offsetting fast by n + 1 keeps a fixed gap so the slow pointer always lands on the predecessor to delete, even when removing the head.
Common Pitfalls
- Advancing fast only n steps causes the removal pointer to land on the wrong node.
- Skipping the dummy head complicates deleting the original first node.
- Not guarding n against list length can throw NullPointerException before fast finishes advancing.
Follow-Up Questions
- How would you delete the k-th node from the end in a single pass when k is provided at runtime repeatedly?
- Can you adapt the approach for doubly linked lists or circular lists?