Remove Nth Node From End of List
Problem
Given the head of a linked list and an integer n, remove the nth node from the end of the list and return its head.
- The number of nodes in the list is at least 1
- 1 ≤ n ≤ the length of the list
Example
head = [1,2,3,4,5], n = 2[1,2,3,5]A naive approach would first compute the length of the list, then remove the (length - n + 1)th node from the start, requiring two passes. The optimal approach uses two pointers spaced n nodes apart. Initially, the right pointer advances n steps ahead. Then both pointers move forward simultaneously until the right pointer reaches the end. At this point, the left pointer is just before the target node. Removing the target node is done by adjusting the left pointer's next reference. This single-pass approach efficiently removes the nth node from the end without computing the list length explicitly.
Approach
Straightforward Solution
A straightforward solution involves two passes: first, traverse the list to find its length; second, traverse again to the (length - n)th node and remove the next node. This approach is O(2n) time and requires two traversals.
Core Observation
The key insight is that the nth node from the end is the (length - n + 1)th node from the start. By maintaining two pointers separated by n nodes, when the leading pointer reaches the end, the trailing pointer is positioned just before the node to remove.
Path to Optimal
To optimize to a single pass, use two pointers. Advance the right pointer n steps ahead. Then move both pointers forward until the right pointer reaches the end. This ensures the left pointer is positioned immediately before the node to remove. This approach eliminates the need to calculate the list length explicitly and reduces time complexity to O(n) with a single traversal.
Optimal Approach
Create a dummy node pointing to the head to handle edge cases gracefully. Initialize two pointers: left at dummy and right at head. Move right pointer n steps forward. Then move both pointers simultaneously until right reaches the end. Adjust left.next to skip the target node. Return dummy.next as the new head.
Time
O(n)
Each pointer traverses the list at most once. The right pointer moves n steps initially, and then both pointers move together until the end, resulting in a single pass through the list.
Space
O(1)
Only a fixed number of pointers and variables are used, regardless of input size, resulting in constant auxiliary space.
Pattern Spotlight
Two Pointers (Fixed Gap)
Maintain two pointers separated by a fixed gap equal to n; when the leading pointer reaches the end, the trailing pointer is positioned just before the target node, enabling single-pass removal.
Solution
| 1 | class Solution:
|
| 2 | def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
|
| 3 | dummy = ListNode(0, head)
|
| 4 | left = dummy
|
| 5 | right = head
|
| 6 |
|
| 7 | while n > 0 and right:
|
| 8 | right = right.next
|
| 9 | n -= 1
|
| 10 |
|
| 11 | while right:
|
| 12 | left = left.next
|
| 13 | right = right.next
|
| 14 |
|
| 15 | left.next = left.next.next
|
| 16 | return dummy.next |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public ListNode removeNthFromEnd(ListNode head, int n) { |
| 5 | ListNode dummy = new ListNode(0, head); |
| 6 | ListNode left = dummy; |
| 7 | ListNode right = head; |
| 8 | |
| 9 | while (n > 0 && right != null) { |
| 10 | right = right.next; |
| 11 | n--; |
| 12 | } |
| 13 | |
| 14 | while (right != null) { |
| 15 | left = left.next; |
| 16 | right = right.next; |
| 17 | } |
| 18 | |
| 19 | left.next = left.next.next; |
| 20 | return dummy.next; |
| 21 | } |
| 22 | } |
| 1 | #include <iostream> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | ListNode* removeNthFromEnd(ListNode* head, int n) { |
| 8 | ListNode* dummy = new ListNode(0, head); |
| 9 | ListNode* left = dummy; |
| 10 | ListNode* right = head; |
| 11 | |
| 12 | while (n > 0 && right != nullptr) { |
| 13 | right = right->next; |
| 14 | n--; |
| 15 | } |
| 16 | |
| 17 | while (right != nullptr) { |
| 18 | left = left->next; |
| 19 | right = right->next; |
| 20 | } |
| 21 | |
| 22 | left->next = left->next->next; |
| 23 | ListNode* result = dummy->next; |
| 24 | delete dummy; |
| 25 | return result; |
| 26 | } |
| 27 | }; |
| 1 | var removeNthFromEnd = function(head, n) { |
| 2 | let dummy = new ListNode(0, head); |
| 3 | let left = dummy; |
| 4 | let right = head; |
| 5 | |
| 6 | while (n > 0 && right !== null) { |
| 7 | right = right.next; |
| 8 | n--; |
| 9 | } |
| 10 | |
| 11 | while (right !== null) { |
| 12 | left = left.next; |
| 13 | right = right.next; |
| 14 | } |
| 15 | |
| 16 | left.next = left.next.next; |
| 17 | return dummy.next; |
| 18 | }; |
Step-by-Step Solution
Create Dummy Node and Initialize Two Pointers
| 3 | dummy = ListNode(0, head)
|
| 4 | left = dummy
|
| 5 | right = head
|
Objective
To set up a dummy node before the head and initialize two pointers to prepare for the fixed-gap traversal.
Key Insight
The dummy node acts as a sentinel to handle edge cases uniformly, such as removing the head node. Initializing the left pointer at dummy and the right pointer at head sets the stage for maintaining a gap of n nodes between them, which is critical for locating the target node in one pass.
Interview Quick-Check
Core Logic
The dummy node ensures that the left pointer can safely move to the node before the one to remove, even if that node is the head.
State & Boundaries
Left starts at dummy, right starts at head, establishing the initial positions for the two-pointer gap.
Advance Right Pointer by n Steps to Establish Gap
| 7 | while n > 0 and right:
|
| 8 | right = right.next
|
| 9 | n -= 1
|
Objective
To move the right pointer n nodes ahead to create a fixed gap between left and right pointers.
Key Insight
Advancing the right pointer n steps ahead ensures that when the right pointer reaches the end of the list, the left pointer will be exactly one node before the target node to remove. This fixed gap is the foundation of the single-pass removal technique.
Interview Quick-Check
Core Logic
Moving the right pointer n steps ahead creates a gap that aligns the left pointer just before the node to remove when right reaches the list's end.
Common Pitfalls & Bugs
Ensure the loop checks both n > 0 and right is not None to avoid null pointer exceptions.
Move Both Pointers Until Right Reaches End
| 11 | while right:
|
| 12 | left = left.next
|
| 13 | right = right.next
|
Objective
To advance both pointers simultaneously until the right pointer reaches the end of the list.
Key Insight
By moving both pointers together, the left pointer maintains its position exactly n nodes behind the right pointer. When the right pointer reaches the end, the left pointer is positioned immediately before the node to remove, enabling direct pointer manipulation to remove the target node.
Interview Quick-Check
Core Logic
Simultaneous movement preserves the gap and positions the left pointer correctly for removal.
State & Boundaries
The loop continues while right is not None, ensuring traversal until the list's end.
Remove Target Node and Return Updated List Head
| 15 | left.next = left.next.next
|
| 16 | return dummy.next |
Objective
To unlink the target node from the list and return the new head.
Key Insight
Adjusting left.next to skip the target node effectively removes it from the list. Returning dummy.next ensures the correct head is returned, even if the original head was removed. This pointer manipulation is the final step that completes the single-pass removal.
Interview Quick-Check
Core Logic
By setting left.next to left.next.next, the target node is bypassed and removed from the list.
Common Pitfalls & Bugs
Failing to return dummy.next instead of head can cause incorrect results when the head node is removed.
Line Analysis
This solution has 1 Critical line interviewers watch for.
left.next = left.next.nextUnlink the target node by skipping it in the list.
This pointer adjustment is the critical step that removes the target node without needing to traverse the list again, enabling the single-pass solution.
dummy = ListNode(0, head)Create a dummy node pointing to the head of the list.
The dummy node simplifies edge cases by providing a stable node before the head, allowing uniform pointer manipulation even when the head is removed.
while n > 0 and right:Begin loop to advance right pointer n steps ahead.
This loop establishes the fixed gap by moving right forward n times, which is essential for locating the target node in one pass.
while right:Begin loop to move both pointers until right reaches the end.
This loop moves both pointers forward in tandem, maintaining the gap and positioning left just before the target node.
return dummy.nextReturn the new head of the list, skipping the dummy node.
Returning dummy.next ensures the correct head is returned, especially when the original head node is removed, maintaining list integrity.
left = dummyInitialize the left pointer to the dummy node.
Positioning left at dummy ensures it can move to the node before the target node, which is necessary for removal.
right = headInitialize the right pointer to the head of the list.
Starting right at head sets the initial position for creating the fixed gap of n nodes between left and right.
right = right.nextMove right pointer to the next node.
Advancing right pointer step-by-step maintains the gap and ensures correct positioning relative to left.
left = left.nextAdvance left pointer to the next node.
Moving left forward keeps the gap consistent and prepares it to unlink the target node.
right = right.nextAdvance right pointer to the next node.
Moving right forward until it reaches the end signals that left is correctly positioned for removal.
n -= 1Decrement n to track steps moved.
Decreasing n ensures the loop terminates after exactly n steps, preserving the intended gap size.
Test Your Understanding
Why is it necessary to use a dummy node at the start of the list?
The dummy node simplifies edge cases, especially when the node to remove is the head of the list, by providing a stable node before the head to adjust pointers safely.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Remove Nth Node From End of List from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Remove Nth Node From End of List drill