Given a head node of a linked list, delete k-th node from the end of the list.
MediumUnlock detailed company stats for this questionUpgrade
Given the head of a linked list, remove the nth node from the end of the list and return the head of the result.
Example 1
Input: head = [1, 2, 3, 4, 5], n = 2 Output: [1, 2, 3, 5]
The second node from the end holds 4.
Example 2
Input: head = [1], n = 1 Output: []
Removing the only node leaves an empty list.
Constraints
- The list has between
1and30nodes. 0 <= Node.val <= 1001 <= n <=the number of nodes in the list.
Approach
If one pointer is n nodes ahead of another, then when the leading pointer reaches the last node, the trailing pointer is n nodes before the end. That's exactly where you need to be to unlink the nth node from the end. Start both pointers at a dummy node placed in front of the head, move the leading pointer n steps, and then move both together until the leading pointer is on the last node. The trailing pointer now sits just before the node to remove, so point it past that node. The dummy node means removing the head needs no special case.
Steps
- Create a dummy node whose
nextishead, and setfastandslowto the dummy. - Move
fastforwardnsteps. - Move both pointers forward until
fast.nextis empty. - Set
slow.next = slow.next.nextand returndummy.next.
Complexity
- Time:
O(L), whereLis the length of the list. One pass. - Space:
O(1).
Common mistakes
- Starting the pointers at the head instead of a dummy node. Removing the first node then needs a special case, and it's easy to miss.
- Moving
fastone step too few or too many. Test withnequal to the length of the list, which removes the head.
Related courses

Course

Course
