Merge K Sorted Lists problem and solution in Java and Python

“Merge K Sorted Lists” is a classic FAANG linked list + heap problem. The idea is to merge k sorted linked lists into one sorted list efficiently.

Problem Statement

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

Goal: Merge all k sorted lists into one sorted list.

1️⃣ Java Solution – Using Min Heap

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class MergeKLists {
    public static ListNode mergeKLists(ListNode[] lists) {
        // Min-heap based on node value
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));

        // Add first node of each list to the heap
        for (ListNode node : lists) {
            if (node != null) minHeap.add(node);
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            tail.next = node;
            tail = node;

            if (node.next != null) {
                minHeap.add(node.next);
            }
        }

        return dummy.next;
    }

    // Helper to print list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode[] lists = new ListNode[3];
        lists[0] = new ListNode(1); lists[0].next = new ListNode(4); lists[0].next.next = new ListNode(5);
        lists[1] = new ListNode(1); lists[1].next = new ListNode(3); lists[1].next.next = new ListNode(4);
        lists[2] = new ListNode(2); lists[2].next = new ListNode(6);

        ListNode merged = mergeKLists(lists);
        printList(merged); // Output: 1 1 2 3 4 4 5 6
    }
}

Time Complexity: O(N log k), where N = total number of nodes, k = number of lists Space Complexity: O(k) for the heap

2️⃣ Python Solution – Using Min Heap

import heapq

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

def mergeKLists(lists):
    min_heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(min_heap, (node.val, i, node))  # use i to avoid tie

    dummy = ListNode(0)
    tail = dummy

    while min_heap:
        val, i, node = heapq.heappop(min_heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(min_heap, (node.next.val, i, node.next))

    return dummy.next

# Helper to print list
def print_list(head):
    while head:
        print(head.val, end=" ")
        head = head.next
    print()

# Example
lists = [
    ListNode(1, ListNode(4, ListNode(5))),
    ListNode(1, ListNode(3, ListNode(4))),
    ListNode(2, ListNode(6))
]

merged = mergeKLists(lists)
print_list(merged)  # Output: 1 1 2 3 4 4 5 6

Notes for Python Heap:

• heapq is a min-heap.
• Use (val, i, node) tuple to avoid comparison errors when val is the same.

⚡ Key Points for FAANG

1. Heap-based approach is efficient: O(N log k) vs brute force O(N log N).
2. Use a dummy node to simplify linked list construction.
3. Be careful with ties in Python heap—use index as a tiebreaker.
4. Alternative: Divide and Conquer merge (merge lists two at a time), also O(N log k).