Remove Nth Node From End of List
The key idea
Keep two pointers a fixed gap of
n nodes apart. Advance fast n steps ahead first, then move both until fast hits the end. slow now sits just before the node to delete, so it can splice it out in a single pass. A dummy head makes deleting the real head a uniform case.Problem
Given the head of a linked list, remove the n-th node from the end of the list and return its head.
The node to remove is counted from the back: when n is 1 you remove the last node, when n equals the list length you remove the first node. After unlinking that node, every other node keeps its original order. A useful trick is a dummy node placed before head so removing the head itself needs no special handling.
The follow-up asks you to do this in one pass over the list rather than first measuring its length and then walking it again.
Constraints
- The number of nodes in the list is
sz. 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
Examples
Input: head = [1,2,3,4,5], n = 2
Output: [1,3,4,5]
Input: head = [1], n = 1
Output: []
Input: head = [1,2], n = 1
Output: [1]
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Linked List problems
- Add Two NumbersMEDIUM
- Copy List with Random PointerMEDIUM
- Design Linked ListMEDIUM
- Insert Greatest Common Divisors in Linked ListMEDIUM
- Intersection of Two Linked ListsEASY
- Maximum Twin Sum of a Linked ListMEDIUM
- Merge Two Sorted ListsEASY
- Odd Even Linked ListMEDIUM
- Partition ListMEDIUM
- Remove Duplicates from Sorted List IIMEDIUM
- Remove Linked List ElementsEASY
- Reorder ListMEDIUM