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

Linked List Cycle

Problem (yeniden ifade)

Tek yönlü bağlı listenin head’i verildiğinde listede bir döngü varsa true, yoksa false döndür. Döngü bir düğümün next’inin önceki bir düğüme dönmesi demektir.

Sezgi

Floyd: slow 1, fast 2 adım. Buluşurlarsa döngü vardır. Fast null’a çarparsa döngü yoktur.

Yaklaşımlar

Floyd döngü tespiti

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. slow=fast=head; fast ve fast.next varken ilerle; eşitlerse true.

Yürüyüş. Uzunluğu k olan döngü: fast döngü içinde her adımda bir düğüm kazanır ve sonunda slow’a denk gelir.

Trade-off. O(1) bellek, ziyaret edilen düğümlerin HashSet’ini (O(n) bellek) yener.

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

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

Düğüm hash kümesi

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. Her düğümü kümeye ekle; tekrar görülürse döngü.

Yürüyüş. Listeyi yürü; herhangi bir düğümün ikinci ziyareti ⇒ true.

Trade-off. Zihnen daha basit; lineer bellek kullanır ve mutasyonsuz O(1) bellek istenirse yasaklanabilir.

Çö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 hasCycleSet(head: ListNode | null): boolean {
  const seen = new Set<ListNode>();
  let cur = head;
  while (cur) {
    if (seen.has(cur)) return true;
    seen.add(cur);
    cur = cur.next;
  }
  return false;
}

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function hasCycleSet(head: ListNode | null): boolean {
  const seen = new Set<ListNode>();
  let cur = head;
  while (cur) {
    if (seen.has(cur)) return true;
    seen.add(cur);
    cur = cur.next;
  }
  return false;
}

Şablon bağlantısı

Kanonik fast & slow döngü tespiti.

Yansıma

Floyd: yavaş +1, hızlı +2. Hızlı null’a düşünce döngü yok. Eşitlik nerede kontrol edilir (adım başı mı sonu mu)?
Tek düğüm self-loop ve iki düğümlük döngü: hızlı ilk adımda kaçar mı?
Listeyi mutasyona uğratmadan O(1) bellek: set ile O(n) bellek trade-off’unu söyle.