Merge K Sorted Lists

Problem

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Examples

The brute-force approach

Collect all node values into an array, sort it, then build a new linked list from the sorted values.

vals = []
for each list in lists:
    while head: vals.append(head.val); head = head.next
vals.sort()
dummy = ListNode(0)
curr = dummy
for v in vals:
    curr.next = ListNode(v)
    curr = curr.next
return dummy.next

O(N log N) where N is total nodes — sorting all values together. Also uses O(N) extra space for the values array.

Spotting the pattern

This is a K-Way Merge problem. The key question to ask yourself:

At any moment, you have one candidate from each of the k lists. Which data structure finds the minimum among k candidates in O(log k)?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.