# My c++ solution, use loser tree, 40ms

• Maybe It's not concise enough. I just want to try loser tree.

``````class Solution {
int k;
int minVal = 1 << 31;
int maxVal = (int)((unsigned int)1 << 31 - 1);
``````

public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
if (lists.empty())
return NULL;

``````    k = lists.size();
if (k == 1)
return lists[0];

vector<int> lose;
vector<int> data;
lose.resize(k);
data.resize(k + 1);
data[k] = minVal;

int i, s;
for (i = 0; i < k; i++) {
lose[i] = k;
data[i] = lists[i] ? lists[i]->val : maxVal;
}

for (i = k - 1; i >= 0; i--) {
}

ListNode first(0);
ListNode *node = &first;

while (data[lose[0]] != maxVal) {
node->next = lists[lose[0]];
node = node->next;
lists[lose[0]] = node->next;
data[lose[0]] = lists[lose[0]] ? lists[lose[0]]->val : maxVal;
}

return first.next;
}

void adjust(int id, vector<int> &data, vector<int> &lose) {
int s, tmp;
for (s = (id + k) / 2; s > 0; s = s / 2) {
if (data[id] > data[lose[s]]) {
tmp = lose[s];
lose[s] = id;
id = tmp;
}
}

lose[0] = id;
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.