Coding · Linked lists
Remove the Nth Node From the End of a Linked List
- Appears on company lists
- Medium
- 2 sources
Company-tagged lists or prep guides name it; no candidate write-up was found.
Solve it in the playground, with tests
You get a singly linked list, written here as an array from head to tail, and a number n. Delete the node that is n places from the tail, where n = 1 means the last node, and return the list that remains. For [1,2,3,4,5] and n = 2 the result is [1,2,3,5]. You may assume 1 <= n <= length, and the list can hold up to 100,000 nodes. The list does not store its length and cannot be walked backwards, so aim to do it in a single pass. This is a guide level question: prep guides list it among Zerodha linked-list topics, and no candidate report of it was found.
Restated in our own words, not a quote from Zerodha or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would say up front that the prep guides I found list this among Zerodha linked-list topics, while no candidate report of it turned up, so it is guide level practice on a standard question. Then I would ask: is n always valid, between 1 and the length? (I assume yes.) May the head itself be the node to remove? Do I modify the list in place and return its head? Does the list store its length? Can I walk it twice, or is one pass required? Values may repeat, and the target is chosen by position, never by value.
Assumptions I would state: n is valid, removal is in place, the length is unknown, and one pass is the goal even though two passes would also be correct.
Brute force
Say the obvious answer and why it is too slow.
Counting from the end for every node is the slowest reading: for each node, walk to the tail to learn its distance, which is O(L²) for a list of L nodes. The natural improvement is two passes. First walk the list to count its length L, then walk again to the node at position L - n - 1 and unlink the node after it, with a special case when the head itself must go.
That is O(L) time and O(1) space and is a fully acceptable first answer. Its weaknesses are the two traversals, which matter if the list arrives as a stream you can read only once, and the special case for removing the head. The one-pass version below removes both.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(L²) by recounting, O(L) in two passes
- Time
- O(L), L is the list length
- Space
- O(1) beyond the list
The pattern is two pointers with a fixed gap. Place a dummy node in front of the head, so the head is no longer special, and start two pointers there, called ahead and behind. Move ahead forward n steps. Now ahead is n nodes in front of behind. Move both one step at a time until ahead is standing on the last node. The gap never changes, so behind is then n nodes before the last one, which makes behind the node just before the target.
Count it to be sure. Number the dummy 0 and the nodes 1 to L. When ahead stands at L, behind stands at L - n, and the node after it, at L - n + 1, is the n-th from the end: n = 1 gives L, the last node. Unlinking is a single assignment, behind.next = behind.next.next, and the result is read from dummy.next.
Why the dummy? If n equals L, the target is the head, so there is no real node before it. With the dummy, behind ends on the dummy and the same assignment drops the head. No case split and no null checks are needed, which is where most bugs on this problem live.
Out loud: "I let one pointer get a head start of n nodes, then move both together. When the leader reaches the end, the follower is exactly one node before the one to delete."
Walk it through
A dry run on the example, step by step.
| Step | Ahead | Behind | What happens |
|---|---|---|---|
| 1 | dummy | dummy | both at the dummy |
| 2 | 2 | dummy | ahead takes n = 2 steps |
| 3 | 3 | 1 | move both |
| 4 | 4 | 2 | move both |
| 5 | 5 | 3 | ahead.next is null: stop |
| 6 | 5 | 3 | unlink 4; result 1,2,3,5 |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
Take [1,2,3,4,5] with n = 2. Both pointers start on the dummy. Ahead walks two steps and lands on node 2, while behind stays on the dummy. Now both advance while ahead has a next node. Ahead moves to 3 and behind to node 1, then ahead to 4 and behind to 2, then ahead to 5 and behind to 3.
Ahead has no next node, so the walk stops with behind on node 3. Node 3's next is 4, the second node from the end, and it is unlinked by pointing 3 at 5. Reading from the dummy gives [1,2,3,5].
The code
Runnable JavaScript, checked against test cases.
function removeNthFromEnd(values, n) {
const dummy = { val: 0, next: null };
let tail = dummy;
for (const value of values) {
tail.next = { val: value, next: null };
tail = tail.next;
}
let ahead = dummy;
for (let step = 0; step < n; step++) ahead = ahead.next;
let behind = dummy;
while (ahead.next !== null) {
ahead = ahead.next;
behind = behind.next;
}
behind.next = behind.next.next;
const result = [];
for (let node = dummy.next; node !== null; node = node.next) result.push(node.val);
return result;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
n = 1: the last node is removed. Ahead reaches the last node after its head start of one step plus the walk, and behind stops on the second to last node.
- n equals the length: the head is removed, and behind stays on the dummy because ahead reaches the last node right after its head start.
- Single node: n must be 1, the only node goes, and the result is an empty list.
- Repeated values: removal is by position, so [7,7,7,7] with n = 2 still loses exactly one node.
- n out of range: not supported. If n exceeds the length, ahead runs past the tail and the code throws. Validate n first if the input is untrusted.
- Long lists: the walk is iterative, so 100,000 nodes cause no stack problem.
Follow-ups to expect
Where the interviewer pushes next.
- How would you solve it with two passes, and when would you prefer that version over the one-pass pointer gap?
- How would you find the middle node of the list in one pass, and how is that related to the fixed gap idea?
- How would you handle an n that may be larger than the length, by returning the list unchanged?
- How would you remove the n-th node from the end of a doubly linked list, and does the answer get simpler?
Where candidates slip
The mistakes this problem punishes.
The most common slip is leaving out the dummy node. The code then needs a separate branch for removing the head, and forgetting it dereferences null.
- Off by one in the gap: moving ahead n + 1 steps while still looping on ahead.next leaves behind one node too early, so the node before the target is deleted. The two conventions work only as a pair: n steps with a test on ahead.next, or n + 1 steps with a test on ahead itself.
- Returning the original head, which is wrong when the head was removed. Return dummy.next.
- Deleting by value, which removes the wrong node when values repeat.
- Counting n from the front by mistake, when n = 1 means the last node.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.