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

Merge Two Sorted Lists

Problem (yeniden ifade)

İki sıralı tek yönlü listenin head’leri verildiğinde, orijinal düğümleri yeniden bağlayarak tek bir sıralı liste üret ve onun head’ini döndür.

Sezgi

Her head, kendi listesindeki kalan en küçük değerdir; küçüğü kuyruğa tak, o listede ilerle. Dummy head, boş liste özel durumunu kaldırır.

Yaklaşımlar

Dummy head iteratif

Doğrulanmadı

Zaman O(n+m)Alan O(1)

Fikir. dummy + tail. İkisi de doluyken küçük head’i tail.next’e bağla ve ilerle. Kalan (null olmayan) listeyi sona ekle.

Yürüyüş. 1→2→4 ve 1→3→4 → 1→1→2→3→4→4.

Trade-off. O(1) ek alan; özyineleme derinliği yok. Mülakattaki kanonik cevap.

Çö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 mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null,
): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      tail.next = list1;
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;
  }
  tail.next = list1 ?? list2;
  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 mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null,
): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      tail.next = list1;
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;
  }
  tail.next = list1 ?? list2;
  return dummy.next;
}

Özyinelemeli birleştirme

Doğrulanmadı

Zaman O(n+m)Alan O(n+m) stack

Fikir. Taban: biri null → diğerini döndür. Değilse küçük head’i seç, .next’ini kalanın birleşimine bağla, onu döndür.

Yürüyüş. Aynı örnek, aynı sonuç; çağrı yığını birleşmiş uzunluğu yansıtır.

Trade-off. En kısa kod, ama O(n+m) yığın uzun listelerde taşabilir. Alan kazancı için iteratif tercih edilir.

Çö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 mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null,
): ListNode | null {
  if (!list1) return list2;
  if (!list2) return list1;
  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  }
  list2.next = mergeTwoLists(list1, list2.next);
  return list2;
}

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

export function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null,
): ListNode | null {
  if (!list1) return list2;
  if (!list2) return list1;
  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  }
  list2.next = mergeTwoLists(list1, list2.next);
  return list2;
}

Şablon bağlantısı

Linked List Manipulation merge-two şablonunun doğrudan uygulaması (dummy head + tail işaretçisi).

Yansıma

Dummy’nin next’i birleşimin başı. Her adımda küçük başı kuyruğa bağla. Biri bitince kalan liste tek parça bağlanır.
Dummy olmazsa ilk düğüm özel durum. İki liste de boşsa cevap null.
Eşit değerde hangisini aldığın sıralı kalır. Özyineleme aynı birleşim, çağrı derinliği n.