Watch 10 video solutions for Remove Nth Node From End of List, a medium level problem involving Linked List, Two Pointers. This walkthrough by NeetCode has 224,470 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1 Output: []
Example 3:
Input: head = [1,2], n = 1 Output: [1]
Constraints:
sz.1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
Follow up: Could you do this in one pass?
Problem Overview: You are given the head of a singly linked list and an integer n. The task is to remove the nth node from the end of the list and return the updated head. The challenge is handling this in a single traversal while safely updating pointers in a linked list.
Approach 1: Two-Pass Technique (O(n) time, O(1) space)
The simplest strategy is to first determine the length of the linked list. Traverse the list once and count how many nodes it contains. Once you know the total length L, the node to remove is at position L - n from the start. Perform a second traversal to reach the node just before this position, then update its next pointer to skip the target node.
This approach works well because pointer updates are straightforward when you know the exact index to remove. Edge cases require attention, especially when the head itself must be removed (n == L). A common trick is introducing a dummy node before the head so that pointer manipulation remains consistent. Time complexity is O(n) due to two full traversals, and space complexity is O(1) since no additional data structures are required.
Approach 2: One-Pass Technique with Fast and Slow Pointers (O(n) time, O(1) space)
The optimal solution uses the two pointers technique. Maintain two pointers called fast and slow. First move the fast pointer n steps ahead of slow. This creates a fixed gap between them. Then move both pointers forward together until fast reaches the end of the list.
Because the gap remains constant, when fast reaches the last node, slow will be positioned right before the node that must be removed. Updating slow.next = slow.next.next removes the target node in constant time. A dummy head node simplifies cases where the first element must be removed. This approach finishes the task in a single traversal with O(n) time complexity and O(1) auxiliary space.
Recommended for interviews: The fast and slow pointer solution is what most interviewers expect. It demonstrates strong understanding of pointer manipulation and efficient traversal patterns in a linked list. The two-pass method is still valuable to explain first because it shows clear reasoning about list length and index transformation. Then follow with the one-pass approach to demonstrate optimization using the two pointers technique.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass Length Counting | O(n) | O(1) | Best for clarity and when computing list length first simplifies reasoning |
| One-Pass Fast and Slow Pointers | O(n) | O(1) | Preferred interview solution when a single traversal is required |