23. Merge k Sorted Lists (Hard)

Problem

You are given an array of k linked lists, each sorted in ascending order. Merge them into one sorted linked list and return its head.

Example

• lists = [[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6]
• lists = [] → []
• lists = [[]] → []

Let N = total number of nodes across all k lists.

LeetCode 23 · Link · Hard

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, dump values, sort, rebuild

Walk every list, collect values, sort, rebuild.

Python

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

def merge_k_lists(lists):
    values = []
    for head in lists:
        while head:
            values.append(head.val)    # L1: O(1) per node, N total
            head = head.next
    values.sort()                      # L2: O(N log N)
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)        # L3: O(1) per node
        tail = tail.next
    return dummy.next

TypeScript

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

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
    const values: number[] = [];
    for (let head of lists) {
        while (head) {
            values.push(head.val);     // L1: O(1) per node, N total
            head = head.next;
        }
    }
    values.sort((a, b) => a - b);     // L2: O(N log N)
    const dummy = new ListNode();
    let tail = dummy;
    for (const v of values) {
        tail.next = new ListNode(v);   // L3: O(1) per node
        tail = tail.next;
    }
    return dummy.next;
}

Go

type ListNode struct {
    Val  int
    Next *ListNode
}

import "sort"

func mergeKLists(lists []*ListNode) *ListNode {
    var values []int
    for _, head := range lists {
        for head != nil {
            values = append(values, head.Val) // L1: O(1) per node, N total
            head = head.Next
        }
    }
    sort.Ints(values)                         // L2: O(N log N)
    dummy := &ListNode{}
    tail := dummy
    for _, v := range values {
        tail.Next = &ListNode{Val: v}         // L3: O(1) per node
        tail = tail.Next
    }
    return dummy.Next
}

Swift

final class Solution {
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        makeList(lists.flatMap(listValues).sorted())
    }
}

Where the time goes, line by line

Variables: k = number of input lists, N = total nodes across all lists.

Line	Per-call cost	Times executed	Contribution
L1 (collect)	$O(1)$	N	$O(N)$
L2 (sort)	$O(N log N)$	1	$O(N log N)$ ← dominates
L3 (rebuild)	$O(1)$	N	$O(N)$

Collecting and rebuilding are both $O(N)$; the sort at L2 is the only superlinear step.

Complexity

• Time: $O(N log N)$, driven by L2.
• Space: $O(N)$.

Ignores sortedness.

Approach 2: Sequential pairwise merge

Merge list 0 with list 1, then the result with list 2, etc.

Python

def merge_two(l1, l2):
    dummy = ListNode()
    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

def merge_k_lists(lists):
    result = None
    for head in lists:                     # L1: k iterations
        result = merge_two(result, head)   # L2: each merge is O(current size)
    return result

TypeScript

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const dummy = new ListNode();
    let tail = dummy;
    while (l1 && 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 ?? l2;
    return dummy.next;
}

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
    let result: ListNode | null = null;
    for (const head of lists) {            // L1: k iterations
        result = mergeTwoLists(result, head);  // L2: each merge is O(current size)
    }
    return result;
}

Go

type ListNode struct {
    Val  int
    Next *ListNode
}

func mergeTwo(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val { tail.Next = l1; l1 = l1.Next } else { tail.Next = l2; l2 = l2.Next }
        tail = tail.Next
    }
    if l1 != nil { tail.Next = l1 } else { tail.Next = l2 }
    return dummy.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
    var result *ListNode
    for _, head := range lists {           // L1: k iterations
        result = mergeTwo(result, head)    // L2: each merge is O(current size)
    }
    return result
}

Swift

final class Solution {
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        var merged: ListNode?
        for list in lists {
            merged = merge(merged, list)
        }
        return merged
    }

    private func merge(_ left: ListNode?, _ right: ListNode?) -> ListNode? {
        let dummy = ListNode()
        var tail = dummy
        var a = left
        var b = right
        while let aNode = a, let bNode = b {
            if aNode.val <= bNode.val {
                tail.next = aNode
                a = aNode.next
            } else {
                tail.next = bNode
                b = bNode.next
            }
            tail = tail.next ?? tail
        }
        tail.next = a ?? b
        return dummy.next
    }
}

Where the time goes, line by line

Variables: k = number of input lists, N = total nodes across all lists.

Line	Per-call cost	Times executed	Contribution
L1 (iterate k lists)	$O(1)$ overhead	k	$O(k)$
L2 (merge_two)	$O(i · N/k)$ for i-th merge	k	$O(k · N)$ ← dominates

The i-th call to merge_two merges a result of size (i-1) · N/k with a list of size N/k, costing $O(i · N/k)$. Summing i from 1 to k gives $O(N/k · k(k+1)$/2) = $O(k · N)$. Early merges are cheap; the final merge is the most expensive.

Complexity

• Time: $O(k · N)$, driven by L2 accumulating work across iterations.
• Space: $O(1)$.

Simple but slow for large k.

Approach 3: Divide-and-conquer pairwise merge (optimal)

Merge lists in pairs like merge sort, $O(log k)$ levels, $O(N)$ work each.

Python

def merge_k_lists(lists):
    if not lists:
        return None
    while len(lists) > 1:           # L1: log k rounds
        merged = []
        for i in range(0, len(lists), 2):   # L2: pair up adjacent lists
            a = lists[i]
            b = lists[i + 1] if i + 1 < len(lists) else None
            merged.append(merge_two(a, b))  # L3: merge each pair
        lists = merged
    return lists[0]

TypeScript

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
    if (!lists.length) return null;
    while (lists.length > 1) {      // L1: log k rounds
        const merged: (ListNode | null)[] = [];
        for (let i = 0; i < lists.length; i += 2) {  // L2: pair up adjacent lists
            const a = lists[i];
            const b = i + 1 < lists.length ? lists[i + 1] : null;
            merged.push(mergeTwoLists(a, b));          // L3: merge each pair
        }
        lists = merged;
    }
    return lists[0];
}

Go

type ListNode struct {
    Val  int
    Next *ListNode
}

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 { return nil }
    for len(lists) > 1 {                      // L1: log k rounds
        var merged []*ListNode
        for i := 0; i < len(lists); i += 2 { // L2: pair up adjacent lists
            a := lists[i]
            var b *ListNode
            if i+1 < len(lists) { b = lists[i+1] }
            merged = append(merged, mergeTwo(a, b)) // L3: merge each pair
        }
        lists = merged
    }
    return lists[0]
}

Swift

final class Solution {
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        guard !lists.isEmpty else { return nil }
        var work = lists
        var interval = 1
        while interval < work.count {
            var index = 0
            while index + interval < work.count {
                work[index] = merge(work[index], work[index + interval])
                index += interval * 2
            }
            interval *= 2
        }
        return work[0]
    }

    private func merge(_ left: ListNode?, _ right: ListNode?) -> ListNode? {
        let dummy = ListNode()
        var tail = dummy
        var a = left
        var b = right
        while let aNode = a, let bNode = b {
            if aNode.val <= bNode.val {
                tail.next = aNode
                a = aNode.next
            } else {
                tail.next = bNode
                b = bNode.next
            }
            tail = tail.next ?? tail
        }
        tail.next = a ?? b
        return dummy.next
    }
}

Where the time goes, line by line

Variables: k = number of input lists, N = total nodes across all lists.

Line	Per-call cost	Times executed	Contribution
L1 (outer loop)	$O(1)$ overhead	log k rounds	$O(log k)$
L2 (pair iteration)	$O(1)$ overhead	k/2 per round	$O(k)$ total
L3 (merge_two per round)	$O(N)$ total per round	log k rounds	$O(N log k)$ ← dominates

At each round, the total work across all pairwise merges is $O(N)$ (every node is touched once). There are log k rounds, giving $O(N log k)$.

Complexity

• Time: $O(N log k)$, driven by L3 across log k rounds.
• Space: $O(log k)$ if implemented recursively; $O(k)$ for the merged array in this iterative form.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 4: Min-heap of heads (optimal)

Put the head of each list in a min-heap keyed by value. Repeatedly pop the smallest and push its next.

Python

import heapq

def merge_k_lists(lists):
    heap = []
    for i, head in enumerate(lists):
        if head:
            # index `i` breaks ties in Python (ListNodes aren't comparable)
            heapq.heappush(heap, (head.val, i, head))  # L1: O(log k) per push
    dummy = ListNode()
    tail = dummy
    while heap:                                          # L2: N iterations total
        val, i, node = heapq.heappop(heap)             # L3: O(log k) per pop
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))  # L4: O(log k)
    return dummy.next

TypeScript

// TypeScript doesn't have a built-in heap; use the divide-and-conquer (Approach 3)
// in interviews. Shown here as a min-heap simulation for illustration.
function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
    // Seed a sorted array of [val, listIndex, node] tuples as a naive heap simulation
    const heap: [number, number, ListNode][] = [];
    for (let i = 0; i < lists.length; i++) {
        if (lists[i]) heap.push([lists[i]!.val, i, lists[i]!]);  // L1: seed
    }
    heap.sort((a, b) => a[0] - b[0]);  // initial sort
    const dummy = new ListNode();
    let tail = dummy;
    while (heap.length) {
        const [, i, node] = heap.shift()!;  // L3: O(k) shift (naive; real heap = O(log k))
        tail.next = node; tail = node;
        if (node.next) {
            heap.push([node.next.val, i, node.next]);  // L4: re-insert
            heap.sort((a, b) => a[0] - b[0]);
        }
    }
    return dummy.next;
}

Swift

private struct ListHeapEntry {
    let value: Int
    let serial: Int
    let node: ListNode
}

final class Solution {
    func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        var heap = BinaryHeap<ListHeapEntry> { left, right in
            left.value == right.value ? left.serial < right.serial : left.value < right.value
        }
        var serial = 0
        for case let node? in lists {
            heap.insert(ListHeapEntry(value: node.val, serial: serial, node: node))
            serial += 1
        }
        let dummy = ListNode()
        var tail = dummy
        while let entry = heap.removeRoot() {
            tail.next = entry.node
            tail = entry.node
            if let next = entry.node.next {
                heap.insert(ListHeapEntry(value: next.val, serial: serial, node: next))
                serial += 1
            }
        }
        tail.next = nil
        return dummy.next
    }
}

Where the time goes, line by line

Variables: k = number of input lists, N = total nodes across all lists.

Line	Per-call cost	Times executed	Contribution
L1 (seed heap)	$O(log k)$	k	$O(k log k)$
L2 (loop)	$O(1)$	N	$O(N)$
L3 (heappop)	$O(log k)$	N	$O(N log k)$ ← dominates
L4 (heappush)	$O(log k)$	up to N	$O(N log k)$

The heap never exceeds k entries (one per list). Each of the N nodes triggers one pop and (conditionally) one push, each costing $O(log k)$.

Complexity

• Time: $O(N log k)$. Each of N pops/pushes on a heap of size at most k (L3/L4).
• Space: $O(k)$ for the heap.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_023.py and run.
# Uses the min-heap approach (Approach 4).
import heapq

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

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

def from_list(vals):
    dummy = ListNode()
    cur = dummy
    for v in vals:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next

def merge_k_lists(lists):
    heap = []
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(heap, (head.val, i, head))
    dummy = ListNode()
    tail = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

def _run_tests():
    # Example: [[1,4,5],[1,3,4],[2,6]] -> [1,1,2,3,4,4,5,6]
    result = merge_k_lists([from_list([1,4,5]), from_list([1,3,4]), from_list([2,6])])
    assert to_list(result) == [1,1,2,3,4,4,5,6]
    # Empty input
    assert merge_k_lists([]) is None
    # Single empty list
    assert to_list(merge_k_lists([None])) == []
    # Single non-empty list
    assert to_list(merge_k_lists([from_list([1,2,3])])) == [1,2,3]
    # Two lists, one empty
    assert to_list(merge_k_lists([from_list([1,2]), None])) == [1,2]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

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

function toList(head: ListNode | null): number[] {
    const out: number[] = [];
    while (head) { out.push(head.val); head = head.next; }
    return out;
}

function fromList(vals: number[]): ListNode | null {
    const dummy = new ListNode();
    let cur = dummy;
    for (const v of vals) { cur.next = new ListNode(v); cur = cur.next; }
    return dummy.next;
}

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const dummy = new ListNode(); let tail = dummy;
    while (l1 && 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 ?? l2; return dummy.next;
}

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
    if (!lists.length) return null;
    while (lists.length > 1) {
        const merged: (ListNode | null)[] = [];
        for (let i = 0; i < lists.length; i += 2)
            merged.push(mergeTwoLists(lists[i], i + 1 < lists.length ? lists[i + 1] : null));
        lists = merged;
    }
    return lists[0];
}

console.assert(JSON.stringify(toList(mergeKLists([fromList([1,4,5]), fromList([1,3,4]), fromList([2,6])]))) === JSON.stringify([1,1,2,3,4,4,5,6]));
console.assert(mergeKLists([]) === null);
console.assert(JSON.stringify(toList(mergeKLists([null]))) === JSON.stringify([]));
console.assert(JSON.stringify(toList(mergeKLists([fromList([1,2,3])]))) === JSON.stringify([1,2,3]));
console.assert(JSON.stringify(toList(mergeKLists([fromList([1,2]), null]))) === JSON.stringify([1,2]));
console.log("all tests pass");

Summary

Approach	Time	Space
Dump + sort + rebuild	$O(N log N)$	$O(N)$
Sequential pairwise	$O(k · N)$	$O(1)$
Divide-and-conquer	$O(N log k)$	$O(k)$ aux
Min-heap of heads	$O(N log k)$	$O(k)$

Both optimal approaches are $O(N log k)$. Use the heap when lists may be very long and you want to avoid deep recursion; use divide-and-conquer when you want pure pointer splicing with no auxiliary structures beyond the recursion stack.

Related data structures

• Linked Lists, pointer splicing
• Heaps / Priority Queues, min-heap of list heads (k-way merge pattern)

Related concepts

• K-way Merge, the multi stream ordering pattern for combining sorted sources.
• Heap and Priority Queue, the priority frontier for repeatedly taking the smallest, largest, or most urgent item.