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

Middle of the Linked List

Problem (yeniden ifade)

Tek yönlü bağlı listenin head’i verildiğinde orta düğümü döndür. İki orta varsa ikincisini döndür.

Sezgi

Slow bir, fast iki adım; fast bitince slow ortadadır.

Yaklaşımlar

Fast & slow pointers

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. Fast null veya fast.next null olana kadar ilerle; slow’u döndür.

Yürüyüş. 1→2→3→4→5 → slow 3’te biter; çift uzunlukta ikinci ortada biter.

Trade-off. Önce uzunluğu saymak iki geçiş; bu tek geçiş O(1) bellek.

Çö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 middleNode(head: ListNode | null): ListNode | null {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow;
}

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

Şablon bağlantısı

Fast & slow: fast bitince slow ortadadır.

Yansıma

Çift uzunlukta ikinci ortaya düşmek için yavaş ve hızlıyı nereden başlatırsın?
Hızlı next.next yokken durmak: fast && fast.next sırası neden önemli?
Uzunluğu sayıp n//2 ilerlemek de doğru; tek geçişin kazancı nedir?