1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct ListNode {
5
    int val;
6
    struct ListNode *next;
7
} ListNode;
8

9
/* —— Custom Min-Heap —— */
10
typedef struct {
11
    ListNode **data;
12
    int size;
13
    int capacity;
14
} MinHeap;
15

16
static void heapSwap(ListNode **a, ListNode **b) {
17
    ListNode *tmp = *a; *a = *b; *b = tmp;
18
}
19

20
static void heapifyUp(MinHeap *h, int i) {
21
    while (i > 0) {
22
        int p = (i - 1) / 2;
23
        if (h->data[p]->val <= h->data[i]->val) break;
24
        heapSwap(&h->data[p], &h->data[i]);
25
        i = p;
26
    }
27
}
28

29
static void heapifyDown(MinHeap *h, int i) {
30
    while (1) {
31
        int left = 2 * i + 1, right = 2 * i + 2, smallest = i;
32
        if (left < h->size && h->data[left]->val < h->data[smallest]->val)
33
            smallest = left;
34
        if (right < h->size && h->data[right]->val < h->data[smallest]->val)
35
            smallest = right;
36
        if (smallest == i) break;
37
        heapSwap(&h->data[i], &h->data[smallest]);
38
        i = smallest;
39
    }
40
}
41

42
static void heapPush(MinHeap *h, ListNode *node) {
43
    h->data[h->size] = node;
44
    heapifyUp(h, h->size);
45
    h->size++;
46
}
47

48
static ListNode* heapPop(MinHeap *h) {
49
    ListNode *res = h->data[0];
50
    h->data[0] = h->data[--h->size];
51
    if (h->size > 0) heapifyDown(h, 0);
52
    return res;
53
}
54

55
ListNode* mergeKLists(ListNode** lists, int listsSize) {
56
    if (listsSize == 0) return NULL;
57

58
    MinHeap h;
59
    h.data = (ListNode**)malloc(sizeof(ListNode*) * listsSize);
60
    h.size = 0;
61
    h.capacity = listsSize;
62

63
    // Push the head nodes of the K linked lists into the heap
64
    for (int i = 0; i < listsSize; i++) {
65
        if (lists[i]) heapPush(&h, lists[i]);
66
    }
67

68
    ListNode dummy;
69
    dummy.next = NULL;
70
    ListNode *tail = &dummy;
71

72
    while (h.size > 0) {
73
        ListNode *minNode = heapPop(&h);
74
        tail->next = minNode;
75
        tail = tail->next;
76
        if (minNode->next) heapPush(&h, minNode->next);
77
    }
78

79
    free(h.data);
80
    return dummy.next;
81
}

1
class ListNode {
2
    constructor(val, next) {
3
        this.val = (val === undefined ? 0 : val);
4
        this.next = (next === undefined ? null : next);
5
    }
6
}
7

8
// Simple implementation using a min-priority queue (manually maintaining a sorted array)
9
function mergeKLists(lists) {
10
    // Filter out empty linked lists, collect all head nodes
11
    const heap = lists.filter(h => h !== null);
12

13
    // Sort by value (simple min-heap substitute)
14
    const sortHeap = () => heap.sort((a, b) => a.val - b.val);
15

16
    const dummy = new ListNode(0);
17
    let tail = dummy;
18

19
    while (heap.length > 0) {
20
        sortHeap();
21
        const minNode = heap.shift(); // Extract the minimum value
22
        tail.next = minNode;
23
        tail = tail.next;
24
        if (minNode.next) heap.push(minNode.next);
25
    }
26

27
    return dummy.next;
28
}
29

30
// Performance-optimized version: divide and conquer (see below)

1
// Merge two sorted linked lists (basic operation)
2
ListNode* mergeTwo(ListNode* a, ListNode* b) {
3
    ListNode dummy;
4
    dummy.next = NULL;
5
    ListNode *tail = &dummy;
6
    while (a && b) {
7
        if (a->val <= b->val) { tail->next = a; a = a->next; }
8
        else                  { tail->next = b; b = b->next; }
9
        tail = tail->next;
10
    }
11
    tail->next = a ? a : b;
12
    return dummy.next;
13
}
14

15
// Divide and conquer: merge in pairs
16
ListNode* mergeKListsDivide(ListNode** lists, int listsSize) {
17
    if (listsSize == 0) return NULL;
18
    // interval represents the current merge step size for each group: 1→2→4→8→...
19
    for (int interval = 1; interval < listsSize; interval *= 2) {
20
        for (int i = 0; i + interval < listsSize; i += interval * 2) {
21
            lists[i] = mergeTwo(lists[i], lists[i + interval]);
22
        }
23
    }
24
    return lists[0];
25
}

1
function mergeTwo(a, b) {
2
    const dummy = new ListNode(0);
3
    let tail = dummy;
4
    while (a && b) {
5
        if (a.val <= b.val) { tail.next = a; a = a.next; }
6
        else                { tail.next = b; b = b.next; }
7
        tail = tail.next;
8
    }
9
    tail.next = a ? a : b;
10
    return dummy.next;
11
}
12

13
function mergeKLists(lists) {
14
    if (lists.length === 0) return null;
15
    const n = lists.length;
16

17
    for (let interval = 1; interval < n; interval *= 2) {
18
        for (let i = 0; i + interval < n; i += interval * 2) {
19
            lists[i] = mergeTwo(lists[i], lists[i + interval]);
20
        }
21
    }
22
    return lists[0];
23
}