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

Odd Even Linked List

Problem (yeniden ifade)

Tek yönlü listenin head’i verildiğinde, konumu tek olan düğümleri önce, çift olanları sonra grupla (1-tabanlı), her grubun iç sırasını koru. Yeniden düzenlenmiş listeyi döndür. O(n) zaman, O(1) ek alan zorunlu.

Sezgi

Bu, değere göre değil indekse göre bir partition. Tek zincir için bir kuyruk, çift zincir için bir kuyruk tut; bir kez yürü; son tek düğümün ardına çift zinciri bağla. Son çift next’i null’lanmazsa döngü oluşur.

Yaklaşımlar

Yerinde tek/çift işaretçi

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. odd = head, even = head.next, evenHead’i sakla. Even’in next’i oldukça: sonraki teki odd.next’e, sonraki çifti even.next’e çek. Sonunda odd.next = evenHead.

Yürüyüş. 1→2→3→4→5. Döngü sonrası: tek 1→3→5, çift 2→4. Dikiş: 1→3→5→2→4.

Trade-off. Kanonik mülakat cevabı. Dummy yok; boş ve tek düğüm doğal çıkar. odd.next = evenHead unutulması kolay.

Çö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 oddEvenList(head: ListNode | null): ListNode | null {
  if (!head) return null;
  let odd = head;
  let even = head.next;
  const evenHead = even;
  while (even && even.next) {
    odd.next = even.next;
    odd = odd.next;
    even.next = odd.next;
    even = even.next;
  }
  odd.next = evenHead;
  return head;
}

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

export function oddEvenList(head: ListNode | null): ListNode | null {
  if (!head) return null;
  let odd = head;
  let even = head.next;
  const evenHead = even;
  while (even && even.next) {
    odd.next = even.next;
    odd = odd.next;
    even.next = odd.next;
    even = even.next;
  }
  odd.next = evenHead;
  return head;
}

İki dummy kuyruk

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. İki sentinel. İndeksle yürü; tek veya çift kuyruğa ekle. even.next = null, sonra odd.next = evenDummy.next. oddDummy.next’i döndür.

Yürüyüş. Aynı liste, aynı sonuç. Sentinel’ler “ilk tek / ilk çift”i sonraki eklemelerle özdeş kılar.

Trade-off. Partition şablonuna daha birebir uyar, hata yapmak zor. Bir çift dummy (hâlâ O(1)). “İki kuyruk, sonda birleştir” diye düşünüyorsan bunu tercih et.

Çö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 oddEvenList(head: ListNode | null): ListNode | null {
  const oddDummy = new ListNode(0);
  const evenDummy = new ListNode(0);
  let odd = oddDummy;
  let even = evenDummy;
  let cur = head;
  let i = 1;
  while (cur) {
    if (i % 2 === 1) {
      odd.next = cur;
      odd = odd.next;
    } else {
      even.next = cur;
      even = even.next;
    }
    cur = cur.next;
    i += 1;
  }
  even.next = null;
  odd.next = evenDummy.next;
  return oddDummy.next;
}

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

export function oddEvenList(head: ListNode | null): ListNode | null {
  const oddDummy = new ListNode(0);
  const evenDummy = new ListNode(0);
  let odd = oddDummy;
  let even = evenDummy;
  let cur = head;
  let i = 1;
  while (cur) {
    if (i % 2 === 1) {
      odd.next = cur;
      odd = odd.next;
    } else {
      even.next = cur;
      even = even.next;
    }
    cur = cur.next;
    i += 1;
  }
  even.next = null;
  odd.next = evenDummy.next;
  return oddDummy.next;
}

Şablon bağlantısı

Linked List Manipulation’ın partition / grup-düğüm şekli: iki dummy kuyruk, sonda birleştir. Yerinde sürüm aynı fikir, sentinel’siz.

Yansıma

Tek ve çift düğümler ayrı kuyruk. Çift listenin başını tek listenin sonuna bağla.
Çift kuyruk null ile bitmeli. Bitmezse tek listeye geri dönen döngü kalır.
Boş ve tek düğüm kendisi. Çift sayıda düğümde son çift, tek listenin sonuna eklenir.