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

Remove Nth Node From End of List

Problem (yeniden ifade)

Tek yönlü bağlı listenin head’i verildiğinde, sondan n. düğümü sil ve head’i döndür.

Sezgi

İki işaretçi arasında n boşluğu tut. Lider null’a varınca takipçi silinecek düğümün hemen önünde durur. Dummy head, ilk düğümü silmeyi basitleştirir.

Yaklaşımlar

Dummy + n boşluğu

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. dummy→head. Dummy’den fast’i n+1 adım ilerlet, sonra fast null olana kadar fast ve slow’u birlikte hareket ettir. slow.next = slow.next.next.

Yürüyüş. Liste 1→2→3→4→5, n=2. Boşluktan sonra 4 silinir.

Trade-off. Tek geçiş, O(1) alan. İki geçiş (önce uzunluk) daha net ama biraz daha fazla kod.

Çözüm

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val; this.next = next;
  }
}
export function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let fast: ListNode | null = dummy;
  let slow: ListNode | null = dummy;
  for (let i = 0; i < n + 1; i++) fast = fast!.next;
  while (fast) { fast = fast.next; slow = slow!.next; }
  slow!.next = slow!.next!.next;
  return dummy.next;
}

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val; this.next = next;
  }
}
export function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let fast: ListNode | null = dummy;
  let slow: ListNode | null = dummy;
  for (let i = 0; i < n + 1; i++) fast = fast!.next;
  while (fast) { fast = fast.next; slow = slow!.next; }
  slow!.next = slow!.next!.next;
  return dummy.next;
}

Şablon bağlantısı

Fast & slow pointers’ın sabit-boşluk varyantı.

Yansıma

Sondan n. düğüm → sabit boşluklu iki pointer. Dummy neden head’i silmeyi tek yola indirir?
n = uzunluk (head silinir) ve n = 1 (kuyruk silinir) hangi dummy/fast yürüyüşünü ister?
Uzunluğu önce sayıp ikinci geçiş de O(n); mülakatta neden tek geçiş istenir?