Given the head of a linked list, remove the nth node from the end of the list and return the head of the modified list. The value n is always valid, meaning it is between 1 and the length of the list inclusive. Try to solve this in a single pass through the list.
Example
head = [1, 2, 3, 4, 5], n = 2
Output: [1, 2, 3, 5]
The 2nd node from the end is 4. Removing it leaves the list as 1 → 2 → 3 → 5.
Use two pointers separated by exactly n+1 nodes. Advance the fast pointer n+1 steps ahead first. Then move both pointers together until fast reaches null — at that point, slow is right before the node to remove. Skip over the target node by adjusting slow's next pointer. A dummy node handles the edge case of removing the head.
Why this works
If you put two pointers n+1 apart and slide them together, when the front pointer falls off the end, the back pointer is exactly one node before the one you want to remove. This finds the nth-from-end in a single pass without needing to know the list length.
Step by step
- Add a dummy node — this lets you handle the case where the head itself is removed, without special logic.
- Advance fast by n+1 — this creates the exact gap needed so that when fast is at null, slow is one node before the target.
- Move both together — advance slow and fast one step at a time until fast reaches null.
- Skip the target node — set
slow.next = slow.next.nextto remove the nth node from the end.
Time: O(n)
Space: O(1)
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head); // handles edge case of removing the head
ListNode slow = dummy;
ListNode fast = dummy;
for (int i = 0; i <= n; i++) { // create n+1 gap so slow lands before target
fast = fast.next;
}
while (fast != null) { // when fast hits null, slow is right before the target
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next; // skip over the node to remove
return dummy.next;
}
}
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0, head); // handles edge case of removing the head
ListNode* slow = &dummy;
ListNode* fast = &dummy;
for (int i = 0; i <= n; i++) { // create n+1 gap so slow lands before target
fast = fast->next;
}
while (fast) { // when fast hits null, slow is right before the target
slow = slow->next;
fast = fast->next;
}
ListNode* toDelete = slow->next;
slow->next = slow->next->next; // skip over the node to remove
delete toDelete;
return dummy.next;
}
};
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head) # handles edge case of removing the head
slow = dummy
fast = dummy
for _ in range(n + 1): # create n+1 gap so slow lands before target
fast = fast.next
while fast: # when fast hits null, slow is right before the target
slow = slow.next
fast = fast.next
slow.next = slow.next.next # skip over the node to remove
return dummy.next