Remove Nth Node From End of List
Understanding the Problem
We need to remove the nth node from the end of a singly linked list. If the list has 5 nodes and n = 2, we remove the 4th node (0-indexed: position 3), which is the second from the end.
The challenge with singly linked lists is that we cannot traverse backward. So "nth from the end" cannot be reached by indexing from the back. We have to identify that node by traversing forward. And to remove a node, we need a pointer to the node before it so we can rewire the next pointer.
One edge case needs care: when n equals the length of the list, we are removing the head itself. There is no node before the head, so this needs separate handling unless we add a dummy node in front of the head.
Key Constraints:
1 <= sz <= 30-> The list is small, so even an O(n^2) solution would pass. Performance is not the constraint that matters here; clean pointer manipulation is.1 <= n <= sz-> n is always valid, so we never have to handle n larger than the list size. The positionlength - nis always non-negative.0 <= Node.val <= 100-> Node values do not affect the algorithm, which works purely on positions.
Approach 1: Two Pass (Count then Remove)
Intuition
If we know the total length of the list, then the nth node from the end is the (length - n + 1)th node from the start (1-indexed). So one pass counts all nodes, and a second pass walks to the node just before the target and rewires pointers.
The one case to handle is removing the head node itself, which happens when n equals the list length. There is no node before the head to rewire. A dummy node placed before the head removes this special case, because the dummy then serves as the predecessor.
Algorithm
- Create a dummy node that points to
head. This handles the edge case where we need to remove the head. - First pass: traverse the entire list to count the total number of nodes (
length). - Calculate the position of the node just before the target: we need to advance
length - nsteps from the dummy. - Second pass: traverse to that position, then set
prev.next = prev.next.nextto skip the target node. - Return
dummy.next(which is the new head).
Example Walkthrough
Code
- Time Complexity: O(n). We traverse the list twice: once to count nodes (O(n)) and once to reach the target position (O(n)). Total is O(2n) which simplifies to O(n).
- Space Complexity: O(1). We only use a few pointers and a counter. No extra data structures.
This approach is correct but traverses the list twice. The next approach finds the same target in a single pass by keeping two pointers spaced n nodes apart.
Approach 2: One Pass (Two Pointers)
Intuition
If we place two pointers n nodes apart and then advance both at the same speed, the gap between them stays at n. When the lead pointer reaches the end, the trailing pointer sits exactly at the node before the one we want to remove.
The two pointers stay a fixed gap apart for the whole traversal. We start both at the dummy node, then advance fast by n + 1 steps. That makes the gap n + 1. After that, both pointers move one step per iteration, so the gap never changes. The loop stops when fast becomes null, meaning fast has moved off the last real node. Since slow trails by n + 1, it stops n + 1 nodes back from that off-the-end position, which is the predecessor of the nth node from the end. Setting slow.next = slow.next.next then drops the target. Starting at the dummy rather than the head is what gives the predecessor for the case where the head itself is removed.
Algorithm
- Create a dummy node pointing to
head. - Initialize both
fastandslowat the dummy node. - Advance
fastbyn + 1steps. Nowfastisn + 1nodes ahead ofslow. - Move both
fastandslowone step at a time untilfastreaches null. - Now
slowis the node just before the target. Setslow.next = slow.next.next. - Return
dummy.next.
Example Walkthrough
Code
- Time Complexity: O(n). We traverse the list exactly once. The fast pointer visits each node, and the slow pointer visits at most n nodes. Total work is O(n).
- Space Complexity: O(1). We use only a dummy node and two pointers. No extra data structures.
Both approaches do O(n) total work. The two-pointer version still touches every node once with the fast pointer, but it avoids the separate counting pass, so it reads the list a single time. That matters when the data is expensive to re-read, such as a stream or a list backed by disk.