#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

/* —— 自定义最小堆 —— */
typedef struct {
    ListNode **data;
    int size;
    int capacity;
} MinHeap;

static void heapSwap(ListNode **a, ListNode **b) {
    ListNode *tmp = *a; *a = *b; *b = tmp;
}

static void heapifyUp(MinHeap *h, int i) {
    while (i > 0) {
        int p = (i - 1) / 2;
        if (h->data[p]->val <= h->data[i]->val) break;
        heapSwap(&h->data[p], &h->data[i]);
        i = p;
    }
}

static void heapifyDown(MinHeap *h, int i) {
    while (1) {
        int left = 2 * i + 1, right = 2 * i + 2, smallest = i;
        if (left < h->size && h->data[left]->val < h->data[smallest]->val)
            smallest = left;
        if (right < h->size && h->data[right]->val < h->data[smallest]->val)
            smallest = right;
        if (smallest == i) break;
        heapSwap(&h->data[i], &h->data[smallest]);
        i = smallest;
    }
}

static void heapPush(MinHeap *h, ListNode *node) {
    h->data[h->size] = node;
    heapifyUp(h, h->size);
    h->size++;
}

static ListNode* heapPop(MinHeap *h) {
    ListNode *res = h->data[0];
    h->data[0] = h->data[--h->size];
    if (h->size > 0) heapifyDown(h, 0);
    return res;
}

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

    MinHeap h;
    h.data = (ListNode**)malloc(sizeof(ListNode*) * listsSize);
    h.size = 0;
    h.capacity = listsSize;

    // 将 K 个链表的头节点入堆
    for (int i = 0; i < listsSize; i++) {
        if (lists[i]) heapPush(&h, lists[i]);
    }

    ListNode dummy;
    dummy.next = NULL;
    ListNode *tail = &dummy;

    while (h.size > 0) {
        ListNode *minNode = heapPop(&h);
        tail->next = minNode;
        tail = tail->next;
        if (minNode->next) heapPush(&h, minNode->next);
    }

    free(h.data);
    return dummy.next;
}

class ListNode {
    constructor(val, next) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

// 使用最小优先队列的简单实现（手动维护排序数组）
function mergeKLists(lists) {
    // 过滤空链表，收集所有头节点
    const heap = lists.filter(h => h !== null);

    // 按值排序（简易最小堆替代）
    const sortHeap = () => heap.sort((a, b) => a.val - b.val);

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

    while (heap.length > 0) {
        sortHeap();
        const minNode = heap.shift(); // 取出最小值
        tail.next = minNode;
        tail = tail.next;
        if (minNode.next) heap.push(minNode.next);
    }

    return dummy.next;
}

// 性能优化版本：分治法（见下方）

// 合并两个有序链表（基础操作）
ListNode* mergeTwo(ListNode* a, ListNode* b) {
    ListNode dummy;
    dummy.next = NULL;
    ListNode *tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }
        else                  { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

// 分治法：两两合并
ListNode* mergeKListsDivide(ListNode** lists, int listsSize) {
    if (listsSize == 0) return NULL;
    // interval 表示当前每组合并的步长：1→2→4→8→...
    for (int interval = 1; interval < listsSize; interval *= 2) {
        for (int i = 0; i + interval < listsSize; i += interval * 2) {
            lists[i] = mergeTwo(lists[i], lists[i + interval]);
        }
    }
    return lists[0];
}

function mergeTwo(a, b) {
    const dummy = new ListNode(0);
    let tail = dummy;
    while (a && b) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else                { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = a ? a : b;
    return dummy.next;
}

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

    for (let interval = 1; interval < n; interval *= 2) {
        for (let i = 0; i + interval < n; i += interval * 2) {
            lists[i] = mergeTwo(lists[i], lists[i + interval]);
        }
    }
    return lists[0];
}