Remove the Nth Node From the End of a Linked List
Solve this Problemhead of a singly linked list and an integer n, remove the nth node from the end of the list (1-indexed) and return the new head.
The tricky part isn't finding the node to remove — it's finding the node just before it, since deletion means rewiring a next pointer, and a singly linked list can't look backward on its own. The optimal solution handles this in one pass with the same head startHead Start (n-Gap) TechniqueAdvance one pointer n steps before starting the second one. The n-node gap between them stays constant as both move together, so when the leading pointer reaches the last node, the trailing pointer sits exactly at the predecessor of the nth-from-end node. technique used for finding the kth node from the end: let fast move n steps ahead, then walk both together until fast.next is null — slow lands exactly where it needs to snip. The one edge case is n equaling the list's length, which means the head itself must go.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of nodes in head ≤ 10⁴ - ◆
-10⁹ ≤ node value ≤ 10⁹ - ◆
n is 1-indexed from the end, and 1 ≤ n ≤ number of nodes
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public Node removeNthFromEnd(Node head, int n) { |
| 3 | Node fast = head; |
| 4 | for (int i = 0; i < n; i++) { |
| 5 | fast = fast.next; |
| 6 | } |
| 7 | if (fast == null) { |
| 8 | return head.next; |
| 9 | } |
| 10 | Node slow = head; |
| 11 | while (fast.next != null) { |
| 12 | slow = slow.next; |
| 13 | fast = fast.next; |
| 14 | } |
| 15 | slow.next = slow.next.next; |
| 16 | return head; |
| 17 | } |
| 18 | } |
| 19 |
1fast starts at head — it needs to move n steps ahead before slow starts moving.
Approach & Solutions
Brute Force — Count Length, Then Traverse to the Predecessor
GoodWalk the list once to count its length. If n equals that length, the node to remove is the head — return head.next directly. Otherwise, the predecessor of the node being removed sits at 0-indexed position (length - n - 1) — walk there in a second pass and bypass the target node. Correct, but it needs the full length before it can even start looking for the node to remove.
O(n)O(1)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node removeNthFromEnd(Node head, int n) {
9 int count = 0;
10 Node curr = head;
11 while (curr != null) {
12 count++;
13 curr = curr.next;
14 }
15 if (n == count) {
16 return head.next;
17 }
18 curr = head;
19 for (int i = 0; i < count - n - 1; i++) {
20 curr = curr.next;
21 }
22 curr.next = curr.next.next;
23 return head;
24 }
25}Optimal — Two Pointers, n Apart, Single Pass
OptimalMove fast n steps ahead first. If it runs off the list entirely, n equals the length, so the head must be removed — return head.next. Otherwise, advance both fast and slow one step at a time until fast.next is null. The fixed n-node gap means slow lands exactly on the predecessor of the node to remove — found in a single pass, no length precomputation needed.
O(n)O(1)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node removeNthFromEnd(Node head, int n) {
9 Node fast = head;
10 for (int i = 0; i < n; i++) {
11 fast = fast.next;
12 }
13 if (fast == null) {
14 return head.next;
15 }
16 Node slow = head;
17 while (fast.next != null) {
18 slow = slow.next;
19 fast = fast.next;
20 }
21 slow.next = slow.next.next;
22 return head;
23 }
24}