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

Problem (yeniden ifade)

Tek yönlü listenin head’i verildiğinde, next işaretçilerini yerinde yeniden bağlayarak listeyi ters çevir ve yeni head’i döndür.

Sezgi

Her düğüm, eskiden kendinden önce gelen düğüme bakmalı. Listeyi bir kez yürü; cur.next’i çevirmeden önce önceki düğümü sakla ki kuyruğu kaybetme.

Yaklaşımlar

Üç işaretçi iteratif

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. prev, cur, nxt. nxt = cur.next kaydet, cur.next = prev yap, sonra prev = cur, cur = nxt. cur null olunca prev yeni head’dir.

Yürüyüş. 1→2→3 → bir adım sonra 1←2 3, sonra 1←2←3. 3’ü döndür.

Trade-off. Şablonun kendisi. O(1) ek alan, yığın riski yok. nxt’i kaydetmeden next’i üzerine yazmak kuyruğu düşürür.

Çö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 reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur = head;
  while (cur) {
    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 reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur = head;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

Özyinelemeli ters

Doğrulanmadı

Zaman O(n)Alan O(n) stack

Fikir. Taban: boş veya tek düğüm zaten ters. head.next üzerinde özyinele; sonra head.next.next = head ve head.next = null ile eski head kuyruk olur.

Yürüyüş. Reverse(1→2→3), Reverse(2→3)=3→2 sonucunu bekler, sonra 1’i 2’ye diker.

Trade-off. Kısa, ama O(n) yığın. Mülakatta özyineleme istenmedikçe iteratif istenir.

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

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

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

Şablon bağlantısı

Linked List Manipulation reverse-whole şeklinin doğrudan uygulaması (prev, cur, nxt üçlüsü).

Yansıma

prev, cur, nxt. Önce sonraki düğümü sakla, cur.next = prev, sonra üçü ilerler. Dönüş prev.
Boş ve tek düğüm kendisi. nxt olmadan next kesilirse kuyruk kaybolur.
Özyineleme aynı ters listeyi kurar, yığın derinliği n.