Remove Nth Node From End of List — Problem & Solution
Remove Nth Node From End of List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Remove Nth Node From End of List is a medium coding problem on two pointers, asked in Amazon, Google, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Two Pointers
- Asked at: Amazon, Google, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the head of a singly linked list and an integer n, remove the n-th node counted from the end of the list (the last node is the 1st from the end), and return the head of the resulting list.
Example 1
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Explanation: The 2nd node from the end holds 4.
Example 2
Input: head = [1], n = 1
Output: []
Explanation: Removing the only node leaves an empty list.
Example 3
Input: head = [1,2], n = 2
Output: [2]
Explanation: The node to remove can be the head itself.
Constraints
The number of nodes in the list is sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
Follow-up: Can you do it in one pass?
Hints for Remove Nth Node From End of List
Hint 1
Counting the length first and then walking
length - nsteps works, in two passes.Hint 2
For one pass, keep two pointers exactly
nnodes apart; when the front one reaches the end, the back one is just before the node to delete.Hint 3
Start both pointers at a dummy node placed before the head, so deleting the head needs no special case.
How to solve Remove Nth Node From End of List
Two pointers with a fixed gap: move fast n nodes ahead of slow, then advance both until fast is on the last node. slow then sits right before the node to remove.
Approach
- Create a dummy node pointing at
head; setfast = slow = dummy. - Advance
fastntimes. - While
fast.nextis not null, advance bothfastandslow. - Unlink with
slow.next = slow.next.nextand returndummy.next.
Why it works
With the dummy at position 0 and the list at positions 1..L, fast ends at position L and slow at L − n, the predecessor of position L − n + 1, which is the n-th node from the end.
Complexity
- Time —
O(L) - Space —
O(1)
Pitfalls
- When n equals the length, the head itself is removed — the dummy node makes that the ordinary case.
- Stopping when
fastis null (instead offast.next) leavesslowone node too far.
Reference solution
Python
from typing import Optional
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.nextJava
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head), fast = dummy, slow = dummy;
for (int i = 0; i < n; i++) fast = fast.next;
while (fast.next != null) { fast = fast.next; slow = slow.next; }
slow.next = slow.next.next;
return dummy.next;
}C++
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0, head);
ListNode *fast = &dummy, *slow = &dummy;
for (int i = 0; i < n; i++) fast = fast->next;
while (fast->next) { fast = fast->next; slow = slow->next; }
slow->next = slow->next->next;
return dummy.next;
}JavaScript
var removeNthFromEnd = function(head, n) {
var dummy = new ListNode(0, head), fast = dummy, slow = dummy;
for (var i = 0; i < n; i++) fast = fast.next;
while (fast.next !== null) { fast = fast.next; slow = slow.next; }
slow.next = slow.next.next;
return dummy.next;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 165 two pointers problems · the whole catalogue
Learn the technique: Two Pointers Technique