#19
Remove Nth Node From End of List
Medium Gap of n between two pointers
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Remove the n-th node from the end of a linked list in one pass and return the head.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: delete the n-th node counted from the end, in one pass.
Why this works: move fast n steps ahead; then move both. When fast hits the end, slow sits right before the target.
Example: 1→2→3→4→5, n = 2
fast ahead by 2when fast is at 5, slow is at 3 → unlink 4 → 1→2→3→5
✦Hints open one at a time
Move a fast pointer n steps ahead first.
Then move both until fast hits the last node; slow is just before the node to remove.
A dummy node handles removing the head.
↗Approach
Start both at a dummy. Advance fast n times, then both together until fast.next is null. Unlink slow.next.
</>Solution (Java)
/**
* class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } // provided by LeetCode
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
for (int i = 0; i < n; i++) fast = fast.next; // open a gap of n
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}!Common mistake
No dummy node — removing the first node (n = length) crashes or returns the wrong head.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Linked List
🎬 Episodes 40–45: video coming soon