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 <= szFollow up: Could you do this in one pass?
The key idea for solving #19 Remove Nth Node From End of List is to locate the node that appears n positions from the end without making multiple passes through the linked list. A common and efficient strategy uses the two-pointer technique.
Start by introducing a dummy node that points to the head of the list. Then move a fast pointer ahead by n steps. After that, move both fast and slow pointers together until the fast pointer reaches the end of the list. At this moment, the slow pointer will be positioned right before the node that needs to be removed.
This method allows the removal operation to be done in a single traversal of the list. Adjust the next pointer of the previous node to skip the target node. The approach runs in O(n) time with O(1) extra space, making it ideal for coding interviews.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers (Single Pass) | O(n) | O(1) |
| Two Pass Counting Approach | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Maintain two pointers and update one with a delay of n steps.
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode
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.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A dummy node simplifies edge cases, especially when the head node itself needs to be removed. By placing a node before the head, pointer updates become consistent and reduce special-case logic.
Yes, this problem is commonly asked in FAANG and other top tech company interviews. It tests knowledge of linked lists, pointer manipulation, and the two-pointer technique, which are core data structure concepts.
A singly linked list is the core data structure used in this problem. Understanding pointer manipulation and node traversal is essential because the task involves modifying the links between nodes efficiently.
The optimal approach uses the two-pointer technique with a dummy node. One pointer moves n steps ahead, and both pointers then move together until the first reaches the end. This ensures the second pointer lands just before the node that must be removed, allowing a single-pass solution.
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.