Remove N-th Node from the End

New·#19·Medium·Linked List

Two pointers held a fixed gap apart

Asked at:AmazonGoogleMicrosoftMeta

Practice mode

Step

Initialization

Both pointers start at the head.

Cache workspace

Fast and Slow Pointers

Step 1 / 7init

100%

list

slow · fast

→

→null

n =

fast =

slow =

Explanation

Rather than measuring the list then walking again, open a gap of exactly 3 between two pointers. When the leader reaches the end, the follower is 3 from it — which is the node to drop.

step 1 / 7

Space play← → stepHome reset

TimeO(n)·SpaceO(1)

Fast and Slow Pointers

1function removeNthFromEnd(head, n) {
2  let fastp = head;//n: 3length: 5
3  let slowp = head;
4 
5  // Open a gap of exactly n
6  for (let i = 0; i < n; i++) {
7    fastp = fastp.next;
8  }
9 
10  // The gap swallowed the list — the head is the target
11  if (fastp === null) {
12    return head.next;
13  }
14 
15  // Move together until fast is on the last node
16  while (fastp.next !== null) {
17    fastp = fastp.next;
18    slowp = slowp.next;
19  }
20 
21  // slow is one before the target
22  slowp.next = slowp.next.next;
23  return head;
24}

length5

Command Palette

Remove N-th Node from the End

Remove N-th Node from the End