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. Since the list is singly linked, you cannot move backward, so the challenge is locating the correct node using forward traversal only.
Approach 1: Two-Pass Technique (Time: O(n), Space: O(1))
This approach first calculates the total length of the linked list. Once you know the length L, the node to remove is at position L - n from the start. Traverse the list once to compute the length, then traverse again to stop right before the node that needs removal. Adjust the next pointer to skip the target node.
The logic is simple and reliable because you convert the "nth from end" requirement into a standard index from the beginning. The tradeoff is that the list is scanned twice. In interviews this is often accepted as a clear baseline solution because it demonstrates correct pointer manipulation and understanding of next references.
Approach 2: One-Pass Technique with Fast and Slow Pointers (Time: O(n), Space: O(1))
This method uses the classic two pointers pattern. Maintain two pointers, fast and slow. Move the fast pointer n steps ahead of slow. Then advance both pointers together until fast reaches the end of the list.
Because the pointers maintain a fixed gap of n nodes, 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 common implementation detail is using a dummy node pointing to the head. This avoids edge cases when the first node itself must be removed. The technique is a standard pattern for problems involving "k distance between pointers" and frequently appears in linked list interview questions.
Recommended for interviews: Interviewers typically expect the one-pass fast/slow pointer approach. The two-pass technique is correct and easy to reason about, but the single traversal solution shows stronger mastery of pointer manipulation and space-efficient algorithms. Demonstrating both approaches during discussion signals that you understand the tradeoff between clarity and optimization.
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass Technique | O(n) | O(1) | Good baseline solution when clarity matters more than traversal count |
| One-Pass Fast and Slow Pointers | O(n) | O(1) | Preferred interview solution; removes the node in a single traversal |
Remove Nth Node from End of List - Oracle Interview Question - Leetcode 19 • NeetCode • 224,470 views views
Watch 9 more video solutions →Practice Remove Nth Node From End of List with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor