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

Reverse Linked List II

Problem (yeniden ifade)

Tek yönlü listenin head’i ve 1-tabanlı left, right indeksleri (left ≤ right) verildiğinde, yalnızca bu aralıktaki alt listeyi ters çevir ve head’i döndür.

Sezgi

Dummy ile left’ten önceki düğüme yürü. Sonra right - left kez, cur’dan sonraki düğümü alıp aralığın başına ekle (head-insertion). cur orijinal left düğümü olarak kalır; öndeki düğümler onun önüne atlar.

Yaklaşımlar

Dummy + aralık ekleme

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. dummy→head. pre’yi left-1 adım ilerlet. cur = pre.next. Aralıktaki her kalan düğüm için: nxt = cur.next; nxt’i çıkar ve pre.next’e tak.

Yürüyüş. 1→2→3→4→5, left=2, right=4. pre 1, cur 2. İlk ekleme: 1→3→2→4→5. İkinci: 1→4→3→2→5.

Trade-off. Tek geçiş, O(1) ek alan. Dummy left = 1’i kapsar. left == right ise döngü boş çalışır. LC 206, aralığın tüm liste olduğu halidir; LC 25 bunu her k-blokta tekrarlar.

Çö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 reverseBetween(
  head: ListNode | null,
  left: number,
  right: number,
): ListNode | null {
  const dummy = new ListNode(0, head);
  let pre = dummy;
  for (let i = 0; i < left - 1; i++) pre = pre.next!;
  const cur = pre.next!;
  for (let i = 0; i < right - left; i++) {
    const nxt = cur.next!;
    cur.next = nxt.next;
    nxt.next = pre.next;
    pre.next = nxt;
  }
  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 reverseBetween(
  head: ListNode | null,
  left: number,
  right: number,
): ListNode | null {
  const dummy = new ListNode(0, head);
  let pre = dummy;
  for (let i = 0; i < left - 1; i++) pre = pre.next!;
  const cur = pre.next!;
  for (let i = 0; i < right - left; i++) {
    const nxt = cur.next!;
    cur.next = nxt.next;
    nxt.next = pre.next;
    pre.next = nxt;
  }
  return dummy.next;
}

Şablon bağlantısı

Linked List Manipulation’ın reverse-range şekli. Tüm liste tersindeki prev / cur / nxt fikri, ama ekleme noktası pre aralığın başında sabitlenir.

Yansıma

left’in öncesine in. [left, right] aralığını çevir, öncekini yeni başa, aralığın kuyruğunu sağa bağla.
left = 1 ise baş değişir; dummy bunu tutar. left = right ise liste aynı.
Sağın başını kaybedersen listenin sonu kopar. Aralık dışındaki düğümler yerinde kalır.