Remove Nth Node From End of List - Solution & Explanation
Problem Statement
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:
- The number of nodes in the list is
sz. 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
Follow up: Could you do this in one pass?
Approach Overview
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 1: Two-Pass Technique
Two-Pass Technique
This approach involves two passes through the linked list to find the node that needs to be removed. In the first pass, compute the length of the list. In the second pass, remove the (Len - n + 1)th node from the start of the list by maintaining a pointer to manage node deletions properly.
This C implementation carries out the Two-Pass Technique. First, it uses a helper function getLength() to compute the length of the list. Then, it iterates to the node immediately before the node to be removed using a dummy node to handle edge cases more efficiently. After removal, it returns the new head of the linked list.
Complexity
Time Complexity: O(L), where L is the length of the linked list since we pass over the list twice (to calculate length and to remove the node).
Space Complexity: O(1) since no additional data structures other than few pointers are used.
Approach 2: One-Pass Technique with Fast and Slow Pointers
One-Pass Technique with Fast and Slow Pointers
This approach uses two pointers, fast and slow. Begin by moving the fast pointer n steps ahead. Then move both pointers simultaneously until fast reaches the end. This provides the correct position to remove the nth node from the end efficiently in one go.
The C implementation employs two pointers, fast and slow, to move through the list. Initially, the fast pointer is moved n+1 steps for gap creation. As both pointers proceed together, the slow pointer effectively lands at the one preceding the removable node. The code adjusts pointers easily when the fast pointer exhausts the list, ensuring the linked list structure remains valid after node removal.
Complexity
Time Complexity: O(L), where L stands for the list's total node count.
Space Complexity: O(1), since a fixed amount of pointers are manipulated.
Approach 3: Fast and Slow Pointers
We define two pointers fast and slow, both initially pointing to the dummy head node of the linked list.
Next, the fast pointer moves forward n steps first, then fast and slow pointers move forward together until the fast pointer reaches the end of the linked list. At this point, the node pointed to by slow.next is the predecessor of the n-th node from the end, and we can delete it.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
Code
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-Pass Technique | Time Complexity: O(L), where L is the length of the linked list since we pass over the list twice (to calculate length and to remove the node). |
| One-Pass Technique with Fast and Slow Pointers | Time Complexity: O(L), where L stands for the list's total node count. |
| Fast and Slow Pointers | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Remove Nth Node from End of List - Oracle Interview Question - Leetcode 19 • NeetCode • 292,781 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Remove Nth Node From End of List easy or hard?
Remove Nth Node From End of List Python/Java solution
How to solve Remove Nth Node From End of List in O(n)?
What is the best approach for Remove Nth Node From End of List?
Is Remove Nth Node From End of List asked at Google/Amazon/Meta?
What data structure is used in Remove Nth Node From End of List?
What is the time complexity of Remove Nth Node From End of List?
Ready to solve this problem?
Practice Remove Nth Node From End of List with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor