Merge k Sorted Lists

hard linked list heap divide and conquer

Problem

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 it.

Push every list head into a min-heap keyed by node value. Repeatedly pop the smallest, append it to the merged tail, and push the popped node's next if any. Each of N total nodes does at most one push and one pop — O(N log k).

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

Output1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

Heap pops the global minimum each step; ties may pop either list.

lists (separate lists by ';', values by ',')

import heapq
def merge_k_lists(lists):
    heap = []
    for i, h in enumerate(lists):
        if h: heapq.heappush(heap, (h.val, i, h))
    dummy = ListNode(); tail = dummy
    while heap:
        v, 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

function mergeKLists(lists) {
  const heap = new MinHeap((a, b) => a[0] - b[0] || a[1] - b[1]);
  for (let i = 0; i < lists.length; i++)
    if (lists[i]) heap.push([lists[i].val, i, lists[i]]);
  const dummy = { next: null }; let tail = dummy;
  while (heap.size()) {
    const [v, i, node] = heap.pop();
    tail.next = node; tail = node;
    if (node.next) heap.push([node.next.val, i, node.next]);
  }
  return dummy.next;
}

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode h : lists) if (h != null) heap.offer(h);
    ListNode dummy = new 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;
}

struct Cmp { bool operator()(ListNode* a, ListNode* b) { return a->val > b->val; } };
ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
    for (auto* h : lists) if (h) heap.push(h);
    ListNode dummy(0); ListNode* tail = &dummy;
    while (!heap.empty()) {
        ListNode* node = heap.top(); heap.pop();
        tail->next = node; tail = node;
        if (node->next) heap.push(node->next);
    }
    return dummy.next;
}

Explanation

You have several lists that are each already sorted, and you want one big sorted list. The smart trick is to always grab the smallest available head across all the lists, and a min-heap (a structure that instantly hands you the smallest item) makes that grab cheap.

First we push the head node of every list into the heap. Then we loop: pop the smallest node, attach it to the back of our answer using a tail pointer, and if that node has a next, push that next back into the heap. This refills the heap with the new front of whichever list we just took from.

It works because the heap always contains exactly the current frontmost unused node of each list. The global minimum must be one of those fronts, so popping the heap minimum is guaranteed to be the next value in sorted order.

Example: lists [1,4,5], [1,3,4], [2,6]. The heap starts with 1, 1, 2. We pop a 1, push its next, pop the other 1, then 2, then 3, and so on, building 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6.

A dummy head keeps the append logic simple, and the heap only ever holds at most k nodes, so each of the N total nodes costs only log k work.

Time: O(N log k) Space: O(k)