Remove Nth Node From End
MediumA gap of n, then move together
Problem
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Send one pointer n steps ahead, then move both together — when it hits the end, you're at the target.
The idea
Put a dummy before the head, advance a lead pointer n+1 nodes, then move both pointers until the lead hits null. The trailing pointer now sits on the predecessor of the node to remove.
The trick
- The dummy makes removing the head require no special case.
- Off-by-one here is the classic bug — the gap must leave you on the predecessor.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — head = [1, 2, 3, 4, 5], n = 2 Values: 1, 2, 3, 4, 5.
1dummy = Node(next=head); fast = dummy; slow = dummy2repeat n+1 times: fast = fast.next3while fast: fast=fast.next; slow=slow.next4slow.next = slow.next.next5return dummy.nextInput
- array
- [1, 2, 3, 4, 5]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- list = 1 -> 2 -> 3 -> 4 -> 5, n = 2
- Output:
- 1 -> 2 -> 3 -> 5
- Explanation:
- The 2nd from the end (4) is removed.
Example 2
- Input:
- list = 1 -> 2, n = 1
- Output:
- 1
- Explanation:
- Drop the last node.
Example 3
- Input:
- list = 1 -> 2 -> 3, n = 3
- Output:
- 2 -> 3
- Explanation:
- Remove the head.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.