Merge K Sorted Lists

Problem

Given an array of K sorted linked-list heads, merge them all into one sorted linked list and return its head.

Constraints

• 0 ≤ k ≤ 10⁴
• 0 ≤ each list.length ≤ 500
• sum of lengths ≤ 10⁴

Approach — Linked List

This is a Linked List problem. The idea: rework the list with careful pointer manipulation — often a dummy head and fast/slow pointers — in a single pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(1) space.

Solution code

Python

import heapq
class Solution:
    def mergeKLists(self, lists):
        h = []
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(h, (node.val, i, node))
        dummy = ListNode()
        cur = dummy
        while h:
            val, i, node = heapq.heappop(h)
            cur.next = node
            cur = node
            if node.next:
                heapq.heappush(h, (node.next.val, i, node.next))
        return dummy.next

Java

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // Min-heap keyed by node value. At any moment, the heap holds
        // the current front of every list that still has nodes left.
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode head : lists) {
            if (head != null) {
                heap.offer(head);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            tail.next = node;
            tail = node;
            if (node.next != null) {
                heap.offer(node.next);
            }
        }
        return dummy.next;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.