#include <bits/stdc++.h>
using namespace std;
// Class to define a ListNode
class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int x) {
        val = x;
        next = nullptr;
    }
};

// Solution class
class Solution {
public:
    // Function to merge two sorted linked lists
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;

        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }

    // Function to merge k sorted lists using divide and conquer
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        return mergeLists(lists, 0, lists.size() - 1);
    }

private:
    // Recursive helper to merge lists between left and right indices
    ListNode* mergeLists(vector<ListNode*>& lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        ListNode* l1 = mergeLists(lists, left, mid);
        ListNode* l2 = mergeLists(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }
};

// Main function for testing
int main() {
    // Create some test lists: [1->4->5], [1->3->4], [2->6]
    ListNode* a = new ListNode(1);
    a->next = new ListNode(4);
    a->next->next = new ListNode(5);

    ListNode* b = new ListNode(1);
    b->next = new ListNode(3);
    b->next->next = new ListNode(4);

    ListNode* c = new ListNode(2);
    c->next = new ListNode(6);

    vector<ListNode*> lists = {a, b, c};
    Solution obj;
    ListNode* result = obj.mergeKLists(lists);

    while (result) {
        cout << result->val << " ";
        result = result->next;
    }

    return 0;
}