Crack the Backend

Problem Statement

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

Key Observations

Min-heap of list heads: Put the first node (head) of each non-null list into a min-heap (compare by node value). Repeatedly: poll the smallest node, append it to the result list, and if that node has a next, push next into the heap. This way we always extend the result with the global minimum among current heads. Time O(N log k) where N = total nodes, k = number of lists; space O(k) for the heap.

Approach

High-level: PriorityQueue<ListNode> by val. Add all non-null heads. While pq not empty: poll min, append to result, if min.next != null offer(min.next). Return dummy.next.

Steps: PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b)->a.val-b.val); for (ListNode h : lists) if (h!=null) pq.offer(h); ListNode dummy = new ListNode(0), tail = dummy; while (!pq.isEmpty()) { ListNode n = pq.poll(); tail.next = n; tail = n; if (n.next!=null) pq.offer(n.next); } return dummy.next;

Implementation

Java

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b) -> a.val - b.val);

    for (ListNode n : lists) {
        if (n != null) {
            pq.offer(n);
        }
    }

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

    while (!pq.isEmpty()) {
        tail.next = pq.poll();
        tail = tail.next;

        if (tail.next != null) {
            pq.offer(tail.next);
        }
    }

    return dummy.next;
}

Test Cases

Example 1

Input

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

Expected

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

Explanation

Merged sorted.

Complexity Analysis

Time: typically O(n log k) or O(n log n).
Space: O(k) or O(n).

Follow-ups

Stream: process one element at a time.