Merge k Sorted Linked Lists

hard linked list heap divide and conquer

Problem

Given k singly-linked lists, each sorted in ascending order, merge them into one sorted list.

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):
    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 mergeK(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 mergeK(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* mergeK(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;
}

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