Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumfast-slow-pointers

Linked List Cycle II

Problem (yeniden ifade)

Tek yönlü bağlı listede döngü varsa döngünün girdiği ilk düğümü döndür; döngü yoksa null. 141’deki evet/hayır yetmez, giriş düğümü gerekir.

Sezgi

Buluşmadan sonra bir işaretçiyi head’den yeniden başlat; aynı hızda girişte buluşurlar.

Yaklaşımlar

Floyd döngü girişi

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. fast/slow ile döngü tespit et; sonra head ve meet eşit olana kadar yürü.

Yürüyüş. Düğüm 2’de başlayan döngü: ikinci faz o düğümü döndürür.

Trade-off. Görülen düğümlerin hash set’i O(n) alan.

Çözüm

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;
}

Şablon bağlantısı

Floyd döngü tespiti, sonra head’den girişe standart 2. faz yürüyüşü.

Yansıma

Döngü tespiti yetmez; giriş düğümü. Neden biri head’e resetlenir ve ikisi +1 yürür?
Döngü yoksa null döndürmeyi unutma. Döngü tüm listeyse giriş head midir?
Kesişme noktası ile giriş arasındaki ilişkiyi (Floyd denklemleri) bir cümlede söyle.