Linked List Manipulation

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

Bağlı liste manipülasyonu pointer yeniden bağlamadır. Yeni düğüm ayırmazsın; mevcut düğümleri yeniden sıralamak için next pointerlarını yeniden atarsın. Temel kural: next’i ezmeden önce eski değeri kaydet, yoksa listenin geri kalanını kaybedersin. Her adımı çiz, off-by-one burada sessiz bir bozulmadır, çökme değil.

Dummy head (sentinel) en yararlı alışkanlıktır. dummy.next’i gerçek head’e yönlendirerek “head’e ekle/sil” özel durumunu ortadan kaldırırsın: her işlem bir “önceki-düğüm” işlemine dönüşür ve yeni head her zaman dummy.next olur.

Şablon şekilleri

Şekil	Temel hamle	Örnek
Tam ters çevirme	prev, cur, nxt üçlüsü	LC 206
[a, b) aralığını ters çevir	cur === b olana kadar ters çevir	LC 92, LC 25 (k-group)
İki sıralıyı birleştir	Dummy + head karşılaştır	LC 21
Partisyon / gruplama	İki dummy kuyruk (sol/sağ), sonunda bağla	LC 328

Karmaşıklık temeli

O(n) zaman, O(1) ekstra alan (birkaç pointer). Temel nokta: listeyi kopyalamaktan kaçın. Yeni liste ayırırsan yavaş yolu yapıyorsun.

Şablondan probleme

1. İşlemi tanımla: ters çevirme, birleştirme, splice, partisyon veya kombinasyonu.
2. Yeni head nerede olacak, değişebiliyorsa dummy ile koru.
3. Yeniden yazmadan önce next’i kaydet; döngüyü önlemek için son next’i null yap.
4. dummy.next’i (veya yakalanan yeni head’i) döndür, eski head referansı asla.

/** Linked list manipulation template: reverse + merge with dummy head. */
export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val; this.next = next;
  }
}

export function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur = head;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

export function mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode();
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}

/** Linked list manipulation template: reverse + merge with dummy head. */
export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val; this.next = next;
  }
}

export function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur = head;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

export function mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode();
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}