Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Fast & Slow Pointers

Guide 1 of 6 · Path 1 of 6

PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumfast-slow-pointers

Remove Nth Node From End of List

Problem (restated)

Given the head of a singly linked list, remove the nth node from the end and return the head.

Intuition

Maintain a gap of n between two pointers. When the leader hits null, the follower sits just before the node to delete. A dummy head simplifies deleting the first node.

Approaches

Dummy + gap of n

Tested only
Time O(n)Space O(1)

Idea. dummy→head. Advance fast n+1 steps from dummy, then move fast and slow together until fast is null. slow.next = slow.next.next.

Walkthrough. List 1→2→3→4→5, n=2. After gap, remove 4.

Trade-offs. One pass, O(1) space. Two-pass (compute length first) is clearer but slightly more code.

Solution
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val; this.next = next;
  }
}
export function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let fast: ListNode | null = dummy;
  let slow: ListNode | null = dummy;
  for (let i = 0; i < n + 1; i++) fast = fast!.next;
  while (fast) { fast = fast.next; slow = slow!.next; }
  slow!.next = slow!.next!.next;
  return dummy.next;
}

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val; this.next = next;
  }
}
export function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let fast: ListNode | null = dummy;
  let slow: ListNode | null = dummy;
  for (let i = 0; i < n + 1; i++) fast = fast!.next;
  while (fast) { fast = fast.next; slow = slow!.next; }
  slow!.next = slow!.next!.next;
  return dummy.next;
}

Template connection

Fixed-gap variant of fast & slow pointers.

Reflection