📖 6 min read
Last updated on

Merge K Sorted Lists — Coding Interview Walkthrough

By intervu.dev

You’re in a coding interview. The interviewer gives you k sorted linked lists and asks you to merge them into one. You start writing a brute-force solution that dumps all values into an array and sorts it. The interviewer says: “That’s O(N log N), but each list is already sorted. Can you exploit that?” You know a heap is involved, but when you push two nodes with the same value into Python’s heapq, it crashes with a TypeError. Now you’re debugging a data structure issue instead of solving the problem.

This walkthrough covers the full solution: the min-heap K-way merge, the Python tiebreaker trick that prevents comparison errors, and the divide-and-conquer alternative worth mentioning.

The Problem

You are given an array of k linked lists, where each list is sorted in ascending order. Merge all of them into a single sorted linked list and return it.

(LeetCode #23)

Example

Input

lists = [
  1 -> 4 -> 5,
  1 -> 3 -> 4,
  2 -> 6
]

Output 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Pick the smallest node from the heads of all lists at each step, producing a single sorted list.

Three sorted linked lists L1=[1,4,5], L2=[1,3,4], L3=[2,6] merging into a single sorted list [1,1,2,3,4,4,5,6].

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

SkillWhat Interviewers Observe
Pattern recognitionDo you recognize this as a heap / priority queue problem?
Complexity analysisCan you articulate why naive approaches fall short?
Data structure fluencyDo you know how and why a min-heap works here?
Linked list mechanicsCan you manipulate pointers correctly without bugs?
Divide & conquer thinkingCan you see the alternative elegant solution?
CommunicationDo you explain trade-offs before committing to an approach?

Step 1: Clarifying Questions

1. Can lists be empty, or can individual lists be empty? Both are possible. An empty array should return None. Individual null lists should be skipped.

2. Are the individual lists guaranteed to be sorted? Yes. This is fundamental to the efficient strategy: you only need to compare heads.

3. Can there be duplicate values across lists? Yes. Your solution must handle duplicates correctly.

4. Can I reuse existing nodes? Yes. Relinking rather than allocating new nodes is standard and expected.

5. What’s the expected scale? For large k and N, you need better than O(N*k).

Step 2: A First (Non-Optimal) Idea

Collect all values, sort, rebuild:

def mergeKLists_brute(lists):
    values = []
    for node in lists:
        while node:
            values.append(node.val)
            node = node.next
    values.sort()
    dummy = ListNode(0)
    curr = dummy
    for v in values:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next

O(N log N) time, O(N) space. Correct but ignores the key structural advantage: each list is already sorted.

Step 3: The Key Insight

At any point in the merge, the next output node must be the smallest among all k current list heads. A min-heap lets you extract that minimum in O(log k) time. Push each head in, pop the smallest, push its successor. Each of the N nodes is pushed and popped once, giving O(N log k) total. Since k <= N, this is always at least as good as sorting, and often dramatically better.

Step 4: Optimal Strategy

  1. Initialize a dummy head and curr pointer.
  2. Push the head of each non-null list into a min-heap, keyed by node value.
  3. While the heap is not empty:
    • Pop the smallest node.
    • Append it to the result.
    • If it has a next, push next into the heap.
  4. Return dummy.next.

Python Implementation

import heapq
from typing import List, Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # (value, index, node) — index breaks ties, avoiding ListNode comparison
        heap = []
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))

        dummy = ListNode(0)
        curr = dummy

        while heap:
            val, i, node = heapq.heappop(heap)
            curr.next = node
            curr = curr.next
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))

        return dummy.next

Why include i in the tuple? Python’s heapq compares tuples element by element. If two nodes share the same value, it tries comparing the ListNode objects, which raises a TypeError. The list index acts as a tiebreaker.

Bonus: Divide & Conquer

def mergeKLists_dc(lists):
    if not lists:
        return None

    def merge_two(l1, l2):
        dummy = ListNode(0)
        curr = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        curr.next = l1 or l2
        return dummy.next

    interval = 1
    while interval < len(lists):
        for i in range(0, len(lists) - interval, interval * 2):
            lists[i] = merge_two(lists[i], lists[i + interval])
        interval *= 2

    return lists[0]

Same O(N log k) time, but O(1) extra space.

Time & Space Complexity

ApproachTimeSpace
Brute force (collect & sort)O(N log N)O(N)
Min-heapO(N log k)O(k)
Divide & conquerO(N log k)O(1) extra

Why O(N log k) beats O(N log N): The heap holds at most k elements, so operations cost O(log k), not O(log N). When k is much smaller than N, this is dramatically faster.

Common Interview Mistakes

  1. Not handling the tuple tiebreaker in Python. Forgetting the list index i causes a TypeError when two nodes share the same value.

  2. Pushing null nodes into the heap. Always check if node before pushing.

  3. Using naive O(N*k) approach. Scanning all k heads linearly for each node gives O(N*k).

  4. Confusing N and k in complexity analysis. N is total nodes, k is number of lists. Be precise.

  5. Not mentioning the divide & conquer alternative. Noting it shows algorithmic maturity.

  6. Forgetting the dummy head pattern. It eliminates messy conditional logic.

What a Strong Candidate Sounds Like

“My approach is a min-heap. At every step, the next output node must be the smallest among all k current heads. A min-heap extracts that minimum in O(log k). I push each list’s head in with a tiebreaker index, pop the minimum, push its successor. Total time is O(N log k), space O(k). I’ll also mention that divide and conquer gets the same time with O(1) extra space.”

Example Interview Dialogue

Interviewer: Why O(N log k) and not O(N log N)?

Candidate: The heap holds at most k elements, so each operation is O(log k). Since k <= N, this is always at least as good as sorting, and significantly better when k is small relative to N.

Interviewer: What if k equals N?

Candidate: Then O(N log k) becomes O(N log N), matching the brute-force sort. The heap still works correctly, it’s just not an improvement. But it’s no worse either.

Interviewer: Can you do it without a heap?

Candidate: Yes, divide and conquer. Repeatedly merge pairs until one list remains. Same O(N log k) time but O(1) extra space. More code but arguably more elegant.

These problems reinforce heaps, K-way merges, and linked list manipulation:

Practice This in a Mock Interview

Reading this explanation gives you the K-way merge pattern and the Python tiebreaker trick. But under time pressure, you’ll need to explain your heap approach, catch the ListNode comparison bug before it bites, and justify your complexity analysis on the fly.

Start a mock interview for Merge K Sorted Lists on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →