Remove Nth Node From End of List
Problem
head of a singly linked list and an integer n,
unlink the node that is n-th from the end (n = 1 is the last node) and return the
head of the resulting list — which changes if the first node is removed.head=[1,2,3,4,5], n=2Output[1,2,3,5]head=[1], n=1Output[]head=[1,2], n=2Output[2]1 ≤ L ≤ 30 · 0 ≤ Node.val ≤ 100 · 1 ≤ n ≤ L · Follow-up: one pass.
Try it yourself
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
}
}
fast starts n+1 nodes ahead of
slow, then when fast runs off the end, slow sits right
before the target. A dummy head makes removing the first node a non-special case.Instinct Nodes joined by next pointers and the task is to reverse, splice, merge, reorder or remove in place - grab a dummy head and rewire pointers carefully.
Memory hack Save next, flip, step - never let go of a rope before you've grabbed the next one.
Open the Linked List Techniques guide →Approaches
Brute ForceArray of Node References
O(L)Space O(L)Copy every node reference into an ArrayList to get random access.
The target is at index L-n; relink its predecessor, or return
head.next when the target is the head.
public ListNode removeNthFromEnd(ListNode head, int n) { List<ListNode> nodes = new ArrayList<>(); for (ListNode c = head; c != null; c = c.next) nodes.add(c); int idx = nodes.size() - n; // index of node to remove if (idx == 0) return head.next; nodes.get(idx - 1).next = nodes.get(idx).next; return head; }
One traversal and trivial indexing, but O(L) extra memory.
BetterTwo Passes (Count, then Walk)
O(L)Space O(1)First pass counts the length L. The predecessor of the target is
L-n steps from a dummy node placed before head, so a
second walk reaches it and skips the target — the dummy covers n = L.
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); int length = 0; for (ListNode c = head; c != null; c = c.next) length++; ListNode prev = dummy; for (int i = 0; i < length - n; i++) prev = prev.next; prev.next = prev.next.next; return dummy.next; }
Constant memory, but walks the list twice — misses the one-pass follow-up.
OptimalOne Pass — Gap of n+1
O(L)Space O(1)Start slow and fast at the dummy and advance
fast n+1 times. Then move both together; the gap never
changes, so when fast becomes null, slow is
exactly n+1 nodes from the end — the target's predecessor.
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); ListNode slow = dummy, fast = dummy; for (int i = 0; i <= n; i++) fast = fast.next; // gap of n+1 while (fast != null) { slow = slow.next; fast = fast.next; } slow.next = slow.next.next; return dummy.next; }
Dry runhead=[1,2,3,4,5], n=2 (D = dummy)
- initDs f12345nullboth at dummy
- gapDs123f45nullfast moved n+1=3
- moveD1s234f5nullstep together
- +2 movesD123s45nullffast null → stop
- unlinkD123s5null3.next = 5 ✔
Single pass, O(1) memory — answers the follow-up.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Array of Node References | O(L) | O(L) |
| Better | Two Passes (Count, then Walk) | O(L) | O(1) |
| Optimal | One Pass — Gap of n+1 | O(L) | O(1) |
- No dummy node —
n == L(remove head) crashes or needs a special case. - Advancing
fastonlynsteps —slowlands on the target, not before it. - Returning
headinstead ofdummy.nextafter the head was removed.
- Ask whether
nis always valid (here 1 ≤ n ≤ L). - Explain the gap invariant rather than just the code.
- Note both O(1) versions are O(L); one pass matters for streams or huge lists.