Remove Nth node from end of Linked List
Problem
Remove the nth node from the end of the list and return the head. Try to do it in one pass.
Example 1
Input: 1 → 2 → 3 → 4 → 5, n = 2 Output: 1 → 2 → 3 → 5
Example 2
Input: 1, n = 1 Output: empty list
Test cases
Case 1
Input: [1,2,3,4,5], 2 Expected: [1,2,3,5]
Case 2
Input: [1], 1 Expected: []
Case 3
Input: [1,2], 1 Expected: [1]
Case 4
Input: [1,2], 2 Expected: [2]
View solutionHide solution1 approach
1. Two pointers, one pass
Time O(n)Space O(1)
Advance a lead pointer n steps, then move both until lead hits the end; trail sits just before the target.
function removeNthFromEnd(head, n) { const dummy = { next: head }; let lead = dummy, trail = dummy; for (let i = 0; i < n; i++) lead = lead.next; while (lead.next) { lead = lead.next; trail = trail.next; } trail.next = trail.next.next; return dummy.next;}