#19 Remove Nth Node From End of List
frequently reported atMetaMicrosoftAmazonBloombergAppleGoogle
the problem
In plain words
Count n nodes back from the tail of a singly linked list and unlink that node. Return the (possibly new) head.
in head = [1,2,3,4,5], n = 2
out [1,2,3,5]
in head = [1], n = 1
out []
in head = [1,2], n = 1
out [1]
- 1 ≤ number of nodes ≤ 30
- 0 ≤ Node.val ≤ 100
- 1 ≤ n ≤ number of nodes
- Follow-up: one pass
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternFast & slow pointersIn-place linked-list rewiring
If fast is n + 1 links ahead of slow, then when fast falls off the end (null), slow sits right before the node to delete.
solutions
From brute force to optimal
n-th from the end is (length − n)-th from the start (0-based).
- Count length L.
- From a dummy, walk L − n hops to the node before the target.
- Unlink it.
Two passes over L nodes.
A counter and a pointer.
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { int length = 0; for (ListNode p = head; p != null; p = p.next) length++; ListNode dummy = new ListNode(0, head); ListNode prev = dummy; for (int i = 0; i < length - n; i++) prev = prev.next; // stop just before the target prev.next = prev.next.next; return dummy.next; }}Advance fast n + 1 times from a dummy, then move both until fast is null.
- dummy → head; fast = slow = dummy.
- Move fast n + 1 steps.
- Move both until fast == null.
- slow.next = slow.next.next; return dummy.next.
fast walks the list once.
Two references plus the dummy.
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); ListNode fast = dummy, slow = dummy; for (int i = 0; i <= n; i++) fast = fast.next; while (fast != null) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return dummy.next; }}Dry run
in the room
How to say it in the interview
talk track
- Explain the dummy: when n equals the length, the head itself is removed and the dummy handles it.
- Explain n + 1 (not n): we need slow to stop before the target so we can unlink it.
traps
- Gap of n instead of n + 1 → slow lands on the target, and a singly linked node can't unlink itself.
- Returning
headafter deleting the head — returndummy.next.
what they ask next
Follow-ups
What if n could be larger than the length?
While opening the gap, check fast != null at every step; if fast runs out first, there is nothing to remove — return the list unchanged.
before you submit
Edge cases to test
- Remove the only node → empty list.
- n equals the length → the head itself is removed.
- n = 1 → the last node is removed.
practise next
Similar problems
- #876Middle of the Linked ListEasyin Linked Lists
- #61Rotate ListMediumin Linked Lists