Remove Nth Node From End of List
Medium · Linked Lists · Linked List · Two Pointers
Problem
Given the head of a singly linked list and an integer n, remove the n-th node counting from the end — the last node is the 1st from the end — and return the head of the resulting list.
n can equal the length of the list, and then the node to remove is the head itself: the list starts at its second node, or is empty if it had only one.
The tests build lists with from_list([...]) and read your answer back with to_list(), both already defined. Lists here run to 50,000 nodes — LeetCode stops at 30 — so a solution that goes one recursive call deeper per node runs out of stack.
Follow-up: can you do it in a single pass over the list?
Examples
Input: head = 1 -> 2 -> 3 -> 4 -> 5, n = 2 Output: 1 -> 2 -> 3 -> 5
Counting from the end, 5 is 1st and 4 is 2nd, so the node holding 4 is removed.
Input: head = 1 -> 2, n = 2 Output: 2
The list has two nodes, so the 2nd from the end is the head. The answer starts at the second node.
Constraints
- 1 <= sz <= 5 * 10^4, where sz is the number of nodes (LeetCode: at most 30)
- 0 <= Node.val <= 100
- 1 <= n <= sz
Approaches
- Keep every node in an array — time O(sz), space O(sz)
Follow-up
Could you do this in a single pass over the list?
Related problems
Start free on Cariara · Coding problems · System design studio
