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 Nodes in k-Group

Problem (yeniden ifade)

Tek yönlü listenin head’i ve bir tamsayı k verildiğinde, listeyi k’lık gruplar halinde ters çevir ve yeni head’i döndür. k’dan kısa kalan sonek orijinal sırada kalır. İşaretçileri yeniden bağla; değer takas etme.

Sezgi

LC 24, bu problemin k = 2 halidir. Her grup için: k düğüm kaldığını doğrula; o koşuyu tüm-liste ters şablonuyla ters çevir; önceki grubun kuyruğunu yeni grup head’ine dik. Grup tamamlanamazsa dur.

Yaklaşımlar

Dummy + k-grup ters

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. dummy→head. groupPrev’den k adım yürüyüp kth’i bul. Yoksa kalan durur. (groupPrev, groupNext) açık aralığını ters çevir ki kth grup head’i olsun; sonra groupPrev eski grup head’i (artık kuyruk) olur.

Yürüyüş. 1→2→3→4→5, k=2. İlk grup: dummy→2→1→3→4→5. İkinci: 1→4→3→5. 5 artar. Sonuç 2→1→4→3→5.

Trade-off. Gerçek O(1) ek alan. Say-sonra-ters mülakat yolu; kısa kalanı ters çevirme. k = 1 no-op; k = n LC 206.

Çö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 reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let groupPrev = dummy;

  const kthFrom = (start: ListNode, n: number): ListNode | null => {
    let cur: ListNode | null = start;
    for (let i = 0; i < n; i++) {
      cur = cur.next;
      if (!cur) return null;
    }
    return cur;
  };

  while (true) {
    const kth = kthFrom(groupPrev, k);
    if (!kth) break;
    const groupNext = kth.next;
    let prev: ListNode | null = groupNext;
    let cur: ListNode | null = groupPrev.next;
    while (cur !== groupNext) {
      const nxt = cur!.next;
      cur!.next = prev;
      prev = cur;
      cur = nxt;
    }
    const newGroupTail = groupPrev.next!;
    groupPrev.next = kth;
    groupPrev = newGroupTail;
  }
  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 reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let groupPrev = dummy;

  const kthFrom = (start: ListNode, n: number): ListNode | null => {
    let cur: ListNode | null = start;
    for (let i = 0; i < n; i++) {
      cur = cur.next;
      if (!cur) return null;
    }
    return cur;
  };

  while (true) {
    const kth = kthFrom(groupPrev, k);
    if (!kth) break;
    const groupNext = kth.next;
    let prev: ListNode | null = groupNext;
    let cur: ListNode | null = groupPrev.next;
    while (cur !== groupNext) {
      const nxt = cur!.next;
      cur!.next = prev;
      prev = cur;
      cur = nxt;
    }
    const newGroupTail = groupPrev.next!;
    groupPrev.next = kth;
    groupPrev = newGroupTail;
  }
  return dummy.next;
}

Özyinelemeli k-grup

Doğrulanmadı

Zaman O(n)Alan O(n/k) stack

Fikir. İleriye k düğüm say. Bitmeden tükenirse head’i olduğu gibi döndür. Yoksa kalan üzerinde özyinele, sonra mevcut k-bloğu o zaten ters soneke ters çevirerek bağla.

Yürüyüş. Aynı liste, k=2: en içte kalan 5; sonra 3→4’ü 5 üzerine, sonra 1→2’yi 4→3→5 üzerine ters çevir.

Trade-off. Yinelemenin en kısa ifadesi, bedeli O(n/k) yığın. Özyineleme istenmedikçe iteratif 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 reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  let node = head;
  for (let i = 0; i < k; i++) {
    if (!node) return head;
    node = node.next;
  }
  let prev = reverseKGroup(node, k);
  let cur = head;
  for (let i = 0; i < k; i++) {
    const nxt = cur!.next;
    cur!.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

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

export function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  let node = head;
  for (let i = 0; i < k; i++) {
    if (!node) return head;
    node = node.next;
  }
  let prev = reverseKGroup(node, k);
  let cur = head;
  for (let i = 0; i < k; i++) {
    const nxt = cur!.next;
    cur!.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

Şablon bağlantısı

Reverse-range’in tekrarlı hali: LC 92 bir kez, LC 24 k=2, bu problem rastgele k. Dummy head hâlâ değişen genel head’i sahiplenir.

Yansıma

Grupta k düğüm yoksa çevirme. Varsa çevir, dummy’ye bağla, sonraki gruba geç.
k = 1 liste aynı. k = uzunluk tüm liste ters. Uzunluk k’ya bölünmüyorsa son parça düz kalır.
Çevrilen grubun yeni başı eski kuyruk. Eski baş, grubun yeni kuyruğu olur.