Remove Nth node from end of Linked List

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}