‹ DS&A interview · Socratic
DSA · Linked List · #118

Merge k Sorted Lists

Module 42 · difficulty 4/5·⏱ 30:00starts on first keystroke

You are given an array of `k` linked-lists `lists`, each linked-list sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return its head. Implement the function `mergeKLists(lists)` where `lists` is an array of list heads (each node is `{ val, next }`, or `null` for an empty list). Return the head of the merged sorted list (or `null` if the result is empty).

Examples
  • lists = [[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6] — Merging the three sorted lists yields one fully sorted list.
  • lists = [] → [] — No lists to merge.
  • lists = [[]] → [] — A single empty list merges to nothing.
Constraints
  • · k == lists.length
  • · 0 <= k <= 10^4
  • · 0 <= lists[i].length <= 500
  • · -10^4 <= node.val <= 10^4
  • · Each lists[i] is sorted in ascending order.
  • · The sum of lists[i].length will not exceed 10^4.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.