Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Heap & Top K

Guide 1 of 6 · Path 1 of 6

PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardheap-top-k

Merge k Sorted Lists

Problem (restated)

Merge k sorted linked lists into one sorted list.

Intuition

Always take the smallest current head among k lists via a min-heap.

Approaches

Min-heap of heads

Tested only
Time O(N log k)Space O(k)

Idea. Heap of (val, list index / node); pop min, push its next.

Walkthrough. [[1,4,5],[1,3,4],[2,6]] → 1→1→2→3→4→4→5→6.

Trade-offs. Heap vs divide-and-conquer merge.

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

export function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const heap: ListNode[] = [];
  const push = (n: ListNode) => {
    heap.push(n);
    heap.sort((a, b) => a.val - b.val);
  };
  for (const h of lists) if (h) push(h);
  const dummy = new ListNode(0);
  let cur = dummy;
  while (heap.length) {
    const n = heap.shift()!;
    cur.next = n;
    cur = n;
    if (n.next) push(n.next);
  }
  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 mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const heap: ListNode[] = [];
  const push = (n: ListNode) => {
    heap.push(n);
    heap.sort((a, b) => a.val - b.val);
  };
  for (const h of lists) if (h) push(h);
  const dummy = new ListNode(0);
  let cur = dummy;
  while (heap.length) {
    const n = heap.shift()!;
    cur.next = n;
    cur = n;
    if (n.next) push(n.next);
  }
  return dummy.next;
}

Template connection

K-way merge with heap.

Pairwise merge

Tested only
Time O(N log k) typical with divide-conquer; O(Nk) if left-foldSpace O(1) extra

Idea. Merge two sorted lists repeatedly. Heap version is cleaner for k-way; pairwise is fine for teaching merge.

Trade-offs. Heap is preferred in interviews for k-way merge clarity.

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

function mergeTwo(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let cur = dummy;
  while (a && b) {
    if (a.val <= b.val) {
      cur.next = a;
      a = a.next;
    } else {
      cur.next = b;
      b = b.next;
    }
    cur = cur.next;
  }
  cur.next = a ?? b;
  return dummy.next;
}

/** Merge lists left-to-right with two-list merge. */
export function mergeKListsPairwise(lists: Array<ListNode | null>): ListNode | null {
  let acc: ListNode | null = null;
  for (const h of lists) acc = mergeTwo(acc, h);
  return acc;
}

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

function mergeTwo(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let cur = dummy;
  while (a && b) {
    if (a.val <= b.val) {
      cur.next = a;
      a = a.next;
    } else {
      cur.next = b;
      b = b.next;
    }
    cur = cur.next;
  }
  cur.next = a ?? b;
  return dummy.next;
}

/** Merge lists left-to-right with two-list merge. */
export function mergeKListsPairwise(lists: Array<ListNode | null>): ListNode | null {
  let acc: ListNode | null = null;
  for (const h of lists) acc = mergeTwo(acc, h);
  return acc;
}

Reflection