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

Palindrome Linked List

Problem (yeniden ifade)

Tek yönlü bağlı listenin değerleri soldan sağa ve sağdan sola aynıysa true döndür. Tek düğüm palindromdur.

Sezgi

Ortayı bul, ikinci yarıyı ters çevir, karşılaştır.

Yaklaşımlar

Orta + ikinci yarıyı ters çevir

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. Slow/fast ile orta; mid.next’ten ters çevir; değerleri karşılaştır.

Yürüyüş. 1→2→2→1 palindrom; 1→2 değil.

Trade-off. Diziye kopyalamak O(n) bellek.

Çözüm

export class ListNode {
  val: number; next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}
function reverse(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null, cur = head;
  while (cur) { const n = cur.next; cur.next = prev; prev = cur; cur = n; }
  return prev;
}
export function isPalindrome(head: ListNode | null): boolean {
  if (!head || !head.next) return true;
  let slow: ListNode | null = head, fast: ListNode | null = head;
  while (fast?.next && fast.next.next) { slow = slow!.next; fast = fast.next.next; }
  let p2 = reverse(slow!.next), p1: ListNode | null = head;
  while (p2) { if (p1!.val !== p2.val) return false; p1 = p1!.next; p2 = p2.next; }
  return true;
}

export class ListNode {
  val: number; next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}
function reverse(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null, cur = head;
  while (cur) { const n = cur.next; cur.next = prev; prev = cur; cur = n; }
  return prev;
}
export function isPalindrome(head: ListNode | null): boolean {
  if (!head || !head.next) return true;
  let slow: ListNode | null = head, fast: ListNode | null = head;
  while (fast?.next && fast.next.next) { slow = slow!.next; fast = fast.next.next; }
  let p2 = reverse(slow!.next), p1: ListNode | null = head;
  while (p2) { if (p1!.val !== p2.val) return false; p1 = p1!.next; p2 = p2.next; }
  return true;
}

Şablon bağlantısı

Fast/slow ile orta, ikinci yarıyı ters çevir, karşılaştır — bağlı liste palindromu.

Yansıma

Ortayı bul, ikinci yarıyı çevir, kıyasla, (isteğe bağlı) geri çevir. Ortadaki tek düğümü kıyas dışı bırakmayı unuttun mu?
O(n) diziye kopyalamak da doğru; O(1) ekstra bellek istenirse çevirme şart.
Tek düğüm ve iki düğüm palindrom/değil uçları.