Merge K sorted linked lists

Intuition

Use a min-heap of size k: initialise with the head of each list. Repeatedly extract the minimum node, add it to the result, and push its successor (if any) back into the heap.

Algorithm

1Min-heap of (node.val, node). Insert head of each non-null list.
2While heap not empty: extract (val, node). Append to result. If node.next != null: push (node.next.val, node.next).
3Return result head.

Example Walkthrough

Input: lists = [1â†’4â†’5, 1â†’3â†’4, 2â†’6]

1.Heap: [(1,L1),(1,L2),(2,L3)]. Extract 1â†’push 4. Extract 1â†’push 3. Extract 2â†’push 6. ...continue...
2.Result: 1â†’1â†’2â†’3â†’4â†’4â†’5â†’6.

Output: [1,1,2,3,4,4,5,6]

Common Pitfalls

•For C# PriorityQueue, compare by node.val to maintain min-heap property.

Merge K sorted linked lists.java

Java

// Approach: Min-heap of size k storing head nodes. Extract min, add its next to heap, repeat.
// Time: O(n log k) Space: O(k)
import java.util.*;

class Node {
    int data;
    Node next;

    Node(int key) {
        data = key;
        next = null;
    }
}

class Solution {
    // Function to merge K sorted linked list.
    Node mergeKLists(List<Node> arr) {
        PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> n1.data - n2.data);
        for (Node node : arr)
            pq.add(node);

        Node head = new Node(-1);
        Node tail = head;

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            tail.next = new Node(node.data);
            node = node.next;
            if (node != null)
                pq.add(node);

            tail = tail.next;
        }

        head = head.next;
        return head;
    }
}

Was this solution helpful?