Given the head of a singly linked list, remove the nth node counting from the end of the list, then return the head of the modified list.
The list is counted 1-indexed from the tail: n = 1 is the last node, and n equal to the list's length removes the first node. After the removal, the surviving nodes keep their original order.
n = 1 is the last node and n = sz is the first node. The problem guarantees 1 <= n <= sz, so you never over-run the list.O(L). The one-pass version just walks the list a single time instead of twice; the asymptotic cost is identical, but it satisfies the classic "can you do it in one pass?" follow-up.fast and slow exactly n nodes apart.Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] The 2nd node from the end is 4 (5 is 1st, 4 is 2nd). Removing it leaves [1,2,3,5].
Input: head = [1], n = 1 Output: [] The only node is both the last and the first — removing it empties the list.
Input: head = [1,2], n = 1 Output: [1] The last node (2) is removed, leaving [1].
- The number of nodes in the list is sz. - 1 <= sz <= 30 - 0 <= Node.val <= 100 - 1 <= n <= sz
Removing a node from the end of a list you can only read from the front is a small puzzle with a beautiful one-pass answer. We'll build up to it: first the honest two-pass version, then the two-pointer trick that measures from the tail without ever knowing the length.
next pointer at a time — you can only move forward, and you don't know the length until you reach the end.In plain words: you're given the front of a chain and a number n. Counting 1 for the last link, 2 for the second-to-last, and so on, unhook the nth link and hand back the front of the repaired chain.
Worked example — head = [1,2,3,4,5], n = 2
count from the end: 5th 4th 3rd 2nd 1st
nodes: 1 → 2 → 3 → 4 → 5
^ 2nd from end
remove node 4: 1 → 2 → 3 → ---→ 5
answer: [1, 2, 3, 5]
Asking before coding shows you've spotted the edge cases an interviewer planted on purpose — it reads as seniority, not hesitation.
“Is n counted from 1 or from 0, and does n = 1 mean the last node?”
Off-by-one here silently removes the wrong node. Confirming that n = 1 is the tail anchors every pointer offset.
“Can n equal the length, meaning I must remove the head itself?”
Removing the head has no predecessor to relink — this is exactly what a dummy node exists to handle.
“Can the list become empty after removal?”
A single-node list with n = 1 returns an empty list, so the caller must handle a null head.
“Is n guaranteed to be within the list length?”
If n could exceed the size, I'd need a guard; the stated 1 <= n <= sz lets me skip that check.
Before I code, a few quick clarifications.
I'll assume n is 1-indexed from the end, so n = 1 removes the last node — is that right?
And I want to flag that when n equals the length I'm removing the head, so I'll use a dummy node to keep that case uniform.
If you knew the length L, the target's position from the front is fixed. For L = 5, n = 2, that's the 5 − 2 + 1 = 4th node. So one honest option is: walk once to learn L, then walk again and stop one node before it.
L = 5, n = 2 → target = (5 - 2 + 1) = 4th from front
Put two pointers exactly n nodes apart. March them forward together. When the leader reaches the last node, the follower is sitting n nodes back — precisely at the node just before your target. You never counted the length; the gap did the measuring for you, in a single pass.
To unlink a node you need its predecessor. The real head has none. Start the follower on a dummy node placed before the head, and even removing the first node becomes an ordinary prev.next = prev.next.next.
| Two pass | One pass | |
|---|---|---|
| Passes over list | 2 | 1 |
| Time | O(L) | O(L) |
| Space | O(1) | O(1) |
Both are linear; the one-pass version simply answers the classic "can you do it in a single traversal?" follow-up. Full code for each is in the Approaches selector below.
Key takeaway
When a problem asks about position from the end of a one-directional structure, a fixed gap between two pointers measures it in a single forward pass — and a dummy node makes deleting the head no different from deleting anything else.
dummy -> head fast = slow = dummy repeat n times: fast = fast.next while fast.next: fast = fast.next; slow = slow.next slow.next = slow.next.next # unlink the target return dummy.next