23. Merge K Sorted ListsHard

Brute Force Linear Scan One by One Min Heap ★D&C Recursive D&C Iterative Pitfalls

Merge K Sorted Lists

HardLinked ListHeapDivide & Conquer·AmazonGoogle

Given an array of k sorted linked lists, merge them into one sorted linked list. Return the head of the merged list.

Example

Input:  lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,3,4,5,6]

Constraints

0 ≤ lists.length ≤ 1000
0 ≤ lists[i].length ≤ 100
-1000 ≤ lists[i][j] ≤ 1000

1. Brute Force — Collect & Sort O(n log n)

Intuition

Ignore the sorted structure entirely. Traverse all k lists and dump every value into an array. Sort that array in O(n log n), then rebuild a single linked list. Simple, but throws away the sorted-order information that each list already provides.

Executing Code

class Solution:

    def mergeKLists(self, lists):

        nodes = []

        for lst in lists:

            while lst:

                nodes.append(lst.val)

                lst = lst.next

        nodes.sort()

        res = ListNode(0); cur = res

        for val in nodes:

            cur.next = ListNode(val)

            cur = cur.next

        return res.next

Time: O(n log n) | Space: O(n)

2. Linear Scan O(n·k)

Intuition

In each round, scan all k current heads to find the minimum, attach it to the result, and advance that list's pointer. Correct and uses O(1) extra space, but scanning k heads for every one of the n total nodes gives O(n·k) — slow for large k.

Executing Code

class Solution:

    def mergeKLists(self, lists):

        res = ListNode(0); cur = res

        while True:

            minNode = -1

            for i in range(len(lists)):

                if not lists[i]: continue

                if minNode == -1 or lists[minNode].val > lists[i].val:

                    minNode = i

            if minNode == -1: break

            cur.next = lists[minNode]

            lists[minNode] = lists[minNode].next

            cur = cur.next

        return res.next

Time: O(n·k) | Space: O(1)

3. Merge One by One O(n·k)

Intuition

Repeatedly merge two lists at a time: merge lists[0] with lists[1], then merge that result with lists[2], and so on. Each merge is the standard O(n) two-list merge. For k lists of average length n/k this still totals O(n·k) because each early merge produces a long list that must be traversed again in subsequent merges.

Executing Code

class Solution:

    def mergeKLists(self, lists):

        if not lists: return None

        for i in range(1, len(lists)):

            lists[i] = self.merge(lists[i-1], lists[i])

        return lists[-1]

    def merge(self, l1, l2):

        dummy = ListNode(0); tail = dummy

        while l1 and l2:

            if l1.val <= l2.val:

                tail.next = l1; l1 = l1.next

            else:

                tail.next = l2; l2 = l2.next

            tail = tail.next

        tail.next = l1 or l2

        return dummy.next

Time: O(n·k) | Space: O(1)

4. Min Heap O(n log k) ★ optimal

Intuition

The bottleneck in the linear scan is finding the minimum among k heads — O(k) per step. A min-heap reduces that to O(log k).

Push all heads into the heap. The heap always exposes the global minimum at index 0.
Pop the min node, attach it to the result, and push its successor (if any) back into the heap.
Heap size stays ≤ k throughout. Each of the n nodes is pushed and popped exactly once: O(n log k) total.

The visualization shows all three layers: the k input lists (consumed nodes grayed), the live heap (sorted left→right, min at the left), and the growing result list.

STEP—

Press ▶ or step forward to begin.

✓

—

Space Play/Pause ·←→ Step ·R Reset ·F Fullscreen

Executing Code

class Solution:

    def mergeKLists(self, lists):

        if not lists: return None

        res = ListNode(0)

        cur = res

        minHeap = []

        for i, lst in enumerate(lists):

            if lst:

                heapq.heappush(minHeap, (lst.val, i, lst))

        while minHeap:

            val, i, node = heapq.heappop(minHeap)

            cur.next = node

            cur = cur.next

            if node.next:

                heapq.heappush(minHeap, (node.next.val, i, node.next))

        return res.next

Time: O(n log k) | Space: O(k)

5. Divide & Conquer — Recursive O(n log k)

Intuition

Mirror merge sort: split the k lists into two halves, recursively merge each half into one sorted list, then merge the two results. At each recursive level all n nodes are touched once, and there are log k levels, giving O(n log k). Unlike merging one-by-one, early merges produce short lists so each node is merged only O(log k) times.

Executing Code

class Solution:

    def mergeKLists(self, lists):

        if not lists: return None

        return self.divide(lists, 0, len(lists) - 1)

    def divide(self, lists, l, r):

        if l == r: return lists[l]

        mid = (l + r) // 2

        left  = self.divide(lists, l, mid)

        right = self.divide(lists, mid + 1, r)

        return self.merge(left, right)

    def merge(self, l1, l2):

        dummy = ListNode(0); cur = dummy

        while l1 and l2:

            if l1.val <= l2.val: cur.next = l1; l1 = l1.next

            else:               cur.next = l2; l2 = l2.next

            cur = cur.next

        cur.next = l1 or l2

        return dummy.next

Time: O(n log k) | Space: O(log k) call stack

6. Divide & Conquer — Iterative O(n log k)

Intuition

Same idea without recursion. In each pass, merge adjacent pairs (0+1, 2+3, 4+5, …) to produce roughly k/2 lists. Repeat until one list remains. This takes O(log k) passes, each touching all n nodes: O(n log k) total, with O(k) extra space for the intermediate list.

Executing Code

class Solution:

    def mergeKLists(self, lists):

        if not lists: return None

        while len(lists) > 1:

            merged = []

            for i in range(0, len(lists), 2):

                l1 = lists[i]

                l2 = lists[i+1] if i+1 < len(lists) else None

                merged.append(self.merge(l1, l2))

            lists = merged

        return lists[0]

    def merge(self, l1, l2):

        dummy = ListNode(0); tail = dummy

        while l1 and l2:

            if l1.val <= l2.val: tail.next = l1; l1 = l1.next

            else:               tail.next = l2; l2 = l2.next

            tail = tail.next

        tail.next = l1 or l2

        return dummy.next

Time: O(n log k) | Space: O(k)

Common Pitfalls

Forgetting to advance the chosen list's pointer: after selecting the minimum node (in linear scan or heap approaches), you must move that list's head to head.next. Skipping this causes an infinite loop.
Wrong heap comparator direction: Python's heapq is a min-heap by default, but Java's PriorityQueue also defaults to min — just make sure the comparator is (a,b) → a.val - b.val, not reversed.
Not handling null / empty lists in input: lists may contain null entries or empty lists. Dereferencing them without a null check causes NPE. Guard before pushing to the heap or accessing .val.
Merge one-by-one vs. pairwise: merging sequentially (0→1→2→…) is O(n·k); pairwise D&C is O(n log k). The difference matters for large k.
Not using a dummy head node: building the result list without a dummy requires special-casing the first node. A dummy node simplifies all append operations uniformly.

Discussion

…

Loading comments…

LeetMotion