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

Fast & Slow Pointers

Guide 3 of 6 · Path 3 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

Linked List Cycle II

Problem (restated)

Return the node where the cycle begins, or null.

Intuition

After meet, restart one pointer at head; same pace meets at entrance.

Approaches

Floyd's cycle entry

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

Idea. Detect cycle with fast/slow; then head and meet walk until equal.

Walkthrough. Cycle starting at node 2: second phase returns that node.

Trade-offs. Hash set of seen nodes is O(n) space.

Solution
export class ListNode {
  val: number; next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}
export function detectCycle(head: ListNode | null): ListNode | null {
  if (!head?.next) return null;
  let slow: ListNode | null = head, fast: ListNode | null = head;
  while (fast?.next) {
    slow = slow!.next; fast = fast.next.next;
    if (slow === fast) {
      let p: ListNode | null = head;
      while (p !== slow) { p = p!.next; slow = slow!.next; }
      return p;
    }
  }
  return null;
}

export class ListNode {
  val: number; next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}
export function detectCycle(head: ListNode | null): ListNode | null {
  if (!head?.next) return null;
  let slow: ListNode | null = head, fast: ListNode | null = head;
  while (fast?.next) {
    slow = slow!.next; fast = fast.next.next;
    if (slow === fast) {
      let p: ListNode | null = head;
      while (p !== slow) { p = p!.next; slow = slow!.next; }
      return p;
    }
  }
  return null;
}

Reflection