Hızlı ve Yavaş İşaretçi

Nasıl düşünülür

İki işaretçi farklı hızlarda (veya sabit ofsetle) ilerler. Hızlı bitince yavaş faydalı bir konumdadır (orta, reset sonrası döngü girişi vb.). Liste uzunluğunu önceden bilmeye gerek yok.

Klasik sonuçlar

• Döngü: buluşurlarsa döngü vardır (Floyd).
• Orta: hızlı sona varınca yavaş ortadadır.
• Sondan n.: hızlıyı n ilerlet, sonra ikisini hızlı bitene kadar yürüt.

Karmaşıklık temeli

O(n) zaman, O(1) ekstra alan, listeyi saklamaya tercih etmenin ana nedeni.

/** Fast/slow template: detect cycle (Floyd). */
export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val; this.next = next;
  }
}
export function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;
  while (fast?.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

/** Fast/slow template: detect cycle (Floyd). */
export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val; this.next = next;
  }
}
export function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;
  while (fast?.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}