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

Swap Nodes in Pairs

Problem (yeniden ifade)

Tek yönlü listenin head’i verildiğinde, her iki komşu düğümü işaretçi yeniden bağlayarak yer değiştir (değerleri takas etme) ve yeni head’i döndür. Artan son düğüm yerinde kalır.

Sezgi

Her takas, çiften önceki düğüme ihtiyaç duyar ki onu ikinci düğüme yönlendirebilesin. Dummy head, ilk çifti sonraki çiftlerle aynı hale getirir. a, b yer değişince sonraki prev artık a’dır (çiftin yeni kuyruğu).

Yaklaşımlar

Dummy ile çift swap

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. dummy→head. İki düğüm kaldıkça: a, b = prev.next, a.next; prev → b → a → b.next olacak şekilde bağla; sonra prev = a.

Yürüyüş. 1→2→3→4. İlk çift: dummy→2→1→3→4. prev=1; ikinci çift: 1→4→3. Sonuç 2→1→4→3.

Trade-off. O(1) ek alan. Dört işaretçiyi (prev, a, b, b.next) çizmeden yazma; kaçan bir atama döngü veya kayıp düğüm üretir.

Çö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 swapPairs(head: ListNode | null): ListNode | null {
  const dummy = new ListNode(0, head);
  let prev = dummy;
  while (prev.next && prev.next.next) {
    const a = prev.next;
    const b = a.next!;
    a.next = b.next;
    b.next = a;
    prev.next = b;
    prev = a;
  }
  return dummy.next;
}

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

export function swapPairs(head: ListNode | null): ListNode | null {
  const dummy = new ListNode(0, head);
  let prev = dummy;
  while (prev.next && prev.next.next) {
    const a = prev.next;
    const b = a.next!;
    a.next = b.next;
    b.next = a;
    prev.next = b;
    prev = a;
  }
  return dummy.next;
}

Özyinelemeli çift swap

Doğrulanmadı

Zaman O(n)Alan O(n) stack

Fikir. Taban: ikiden az düğüm. nxt ikinci düğüm; head.next = swapPairs(nxt.next), sonra nxt.next = head. Yeni çift head’i olarak nxt’i döndür.

Yürüyüş. Aynı liste: en iç çağrı 3→4’ü 4→3 yapar, sonra 1↔2 ve 1.next 4’e bakar.

Trade-off. Kısa, ama O(n/2) yığın karesi. Mülakatta varsayılan iteratiftir; özyineleme temiz bir devam sorusu.

Çö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 swapPairs(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;
  const nxt = head.next;
  head.next = swapPairs(nxt.next);
  nxt.next = head;
  return nxt;
}

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

export function swapPairs(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;
  const nxt = head.next;
  head.next = swapPairs(nxt.next);
  nxt.next = head;
  return nxt;
}

Şablon bağlantısı

Linked List Manipulation’ın grup-swap şekli: dummy head artı uzunluğu 2 olan yerel ters. LC 25 aynı fikri k’ya geneller.

Yansıma

Çift a -> b iken b -> a. Dummy, baş çift değişince yeni başı tutar.
Tek kalan son düğüm yerinde kalır. Boş liste ve tek düğüm kendisi.
next’i saklamadan kesersen kuyruk kaybolur. Özyineleme aynı çiftleri çevirir.