Definition
- Two-pointer gap – fast pointer leads slow pointer by exactly N+1 nodes so slow stops one node before the target.
- Dummy head – a sentinel before the real head so that deleting the first node needs no special case.
- Unlink –
slow.next = slow.next.nextremoves the target by skipping it in the chain. - Complexity – O(n) time, O(1) space, single pass.
- Validation – if N exceeds the list length, fast runs past null and the code must handle that gracefully.
Rajesh wants to cancel the third-from-last scheduled transfer in his pending queue, but the queue has no length counter. A clerk puts one finger on the first slip, then moves a second finger three slips ahead. Both fingers slide forward together until the leading finger falls off the end. The trailing finger is now sitting right before the slip to cancel, so the clerk pulls that slip out and reconnects the chain.
Understanding the Concepts
What is the remove Nth from end problem?
Given the head of a singly linked list, remove the Nth node from the end and return the new head. The challenge is that a singly linked list has no backward links, so you cannot count from the end directly. The two-pointer gap technique solves this in a single pass.
package com.bank.model;
import java.math.BigDecimal;
public class TransferNode {
public String transferId;
public BigDecimal amount;
public TransferNode next;
public TransferNode(String transferId, BigDecimal amount) {
this.transferId = transferId;
this.amount = amount;
}
}
How does the two-pointer gap technique work?
Create a dummy node before the head. Set both fast and slow to the dummy. Advance fast by N+1 steps. Then move both pointers one step at a time until fast becomes null. Now slow is the node just before the target. Unlink with slow.next = slow.next.next.
package com.bank.service;
import com.bank.model.TransferNode;
import java.math.BigDecimal;
public class RemoveNthFromEnd {
public static TransferNode removeNthFromEnd(TransferNode head, int n) {
TransferNode dummy = new TransferNode("DUMMY", BigDecimal.ZERO);
dummy.next = head;
TransferNode fast = dummy;
TransferNode slow = dummy;
// Advance fast by n+1 steps
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// Move both until fast is null
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// Unlink the target node
System.out.println("Removing: " + slow.next.transferId);
slow.next = slow.next.next;
return dummy.next;
}
public static void main(String[] args) {
TransferNode h = new TransferNode("TRF-001", new BigDecimal("10000"));
h.next = new TransferNode("TRF-002", new BigDecimal("25000"));
h.next.next = new TransferNode("TRF-003", new BigDecimal("50000"));
h.next.next.next = new TransferNode("TRF-004", new BigDecimal("75000"));
// Remove 2nd from end (TRF-003)
TransferNode result = removeNthFromEnd(h, 2);
TransferNode cur = result;
while (cur != null) {
System.out.println(cur.transferId + " : " + cur.amount);
cur = cur.next;
}
}
}
Removing: TRF-003
TRF-001 : 10000
TRF-002 : 25000
TRF-004 : 75000
Why use a dummy head?
The dummy head handles the edge case where N equals the list length, meaning you must delete the head itself. Without the dummy, deleting the head requires a separate if branch. With the dummy, the same slow.next = slow.next.next code works for all positions.
// Without dummy: special case needed when removing head
if (n == length) {
return head.next; // skip the head
}
// With dummy: same code handles everything
TransferNode dummy = new TransferNode("DUMMY", BigDecimal.ZERO);
dummy.next = head;
// ... gap logic ...
slow.next = slow.next.next; // works even when removing head
return dummy.next;
Why advance fast by N+1 instead of N?
Because both pointers start at the dummy (one node before the real head), advancing fast by N+1 creates the right gap so that when fast reaches null, slow is positioned one node before the target. If you advanced by only N, slow would land on the target itself, and in a singly linked list you cannot unlink a node you are standing on.
Dummy -> [1] -> [2] -> [3] -> [4] -> null n = 2 After advancing fast by n+1 = 3 steps: slow = Dummy fast = [3] Move both until fast = null: slow = [2], fast = null slow.next = [3] which is the 2nd from end → remove it
What about input validation?
If N is larger than the list length, advancing fast by N+1 steps runs past null and throws a NullPointerException. Production code should validate N.
public static TransferNode removeNthSafe(TransferNode head, int n) {
TransferNode dummy = new TransferNode("DUMMY", BigDecimal.ZERO);
dummy.next = head;
TransferNode fast = dummy;
for (int i = 0; i <= n; i++) {
if (fast == null) {
System.out.println("N=" + n + " exceeds list length. No removal.");
return head;
}
fast = fast.next;
}
TransferNode slow = dummy;
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
How is this different from the two-pass approach?
The two-pass approach first counts the total length L, then walks to position L-N to find the node before the target. Both approaches are O(n) time and O(1) space, but the two-pointer gap does it in a single pass.
| Approach | Passes | Time | Space |
|---|---|---|---|
| Two-pointer gap | 1 | O(n) | O(1) |
| Count then walk | 2 | O(n) | O(1) |
// Two-pass approach
public static TransferNode removeNthTwoPass(TransferNode head, int n) {
int length = 0;
TransferNode cur = head;
while (cur != null) { length++; cur = cur.next; }
TransferNode dummy = new TransferNode("DUMMY", BigDecimal.ZERO);
dummy.next = head;
cur = dummy;
for (int i = 0; i < length - n; i++) {
cur = cur.next;
}
cur.next = cur.next.next;
return dummy.next;
}
What are the edge cases?
Single-node list (removing the only node), removing the head, and removing the tail are the key edge cases.
package com.bank.service;
import com.bank.model.TransferNode;
import java.math.BigDecimal;
public class RemoveNthEdgeCases {
public static void main(String[] args) {
// Single node: remove 1st from end
TransferNode single = new TransferNode("TRF-001", new BigDecimal("1000"));
TransferNode result = RemoveNthFromEnd.removeNthFromEnd(single, 1);
System.out.println("Single removed: " + (result == null ? "empty list" : result.transferId));
// Remove head (4th from end in a 4-node list)
TransferNode h = new TransferNode("A", new BigDecimal("100"));
h.next = new TransferNode("B", new BigDecimal("200"));
h.next.next = new TransferNode("C", new BigDecimal("300"));
h.next.next.next = new TransferNode("D", new BigDecimal("400"));
result = RemoveNthFromEnd.removeNthFromEnd(h, 4);
System.out.println("After removing head: " + result.transferId);
}
}
Removing: TRF-001
Single removed: empty list
Removing: A
After removing head: B
What should a senior engineer know?
The two-pointer gap is a pattern that extends beyond removal. The same gap idea finds the Kth node from the end, checks if a list has at least N nodes, and even helps with sliding window problems on linked lists.
In production at National Bank of India, Rajesh keeps a queue of scheduled future transfers. When he cancels the Nth-from-last transfer, the service validates N against the queue length during the fast-pointer advance phase, returning an error response rather than crashing if N is out of bounds.
// Reuse the gap idea to find (not remove) the Nth from end
public static TransferNode findNthFromEnd(TransferNode head, int n) {
TransferNode fast = head;
for (int i = 0; i < n; i++) {
if (fast == null) return null;
fast = fast.next;
}
TransferNode slow = head;
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
Visual Overview
Two-Pointer Gap Technique (n=2) Dummy ──> [TRF-001] ──> [TRF-002] ──> [TRF-003] ──> [TRF-004] ──> null Step 1: Advance fast by n+1 = 3 slow = Dummy fast = [TRF-003] Step 2: Move both until fast = null slow = [TRF-002], fast = null Step 3: Unlink slow.next (TRF-003) Dummy ──> [TRF-001] ──> [TRF-002] ──> [TRF-004] ──> null
Edge Case: Removing Head (n = list length) Dummy ──> [A] ──> [B] ──> [C] ──> null n = 3, advance fast by 4 steps slow = Dummy, fast = null Unlink Dummy.next (A) Dummy ──> [B] ──> [C] ──> null Return Dummy.next = [B]
Key Takeaway
Removing the Nth node from the end of a singly linked list in one pass uses the two-pointer gap technique. You create a dummy node before the head, advance a fast pointer N+1 steps ahead, then slide both fast and slow forward until fast falls off the end. The gap stays fixed, so slow lands exactly on the node before the target, and you unlink the target with a single slow.next = slow.next.next.
The dummy head is what makes this clean. Without it, removing the head node (when N equals the list length) needs a separate code path. With the dummy, every position is handled by the same logic, and you return dummy.next at the end.
The advance by N+1 rather than N is a common source of confusion. Both pointers start at the dummy, which is one position before the real head, so the extra step ensures slow ends up one node before the target rather than on the target itself. In a singly linked list you cannot unlink a node you are standing on because you need access to the previous node's next pointer.
In production at National Bank of India, Rajesh cancels scheduled transfers by position from the end. The service validates N during the advance phase and returns a safe error if N exceeds the queue length, rather than allowing a NullPointerException to crash the request. The gap technique answers in one pass, which matters for long queues under live request latency constraints.
Remember one sentence: advance fast N+1 from dummy, walk both to the end, slow lands before the target, unlink in one step.
---