leetcode

0 // Naive solution, barely passed

1 class Solution {

2 public:

3 ListNode *mergeKLists(vector<ListNode *> &lists) {

4 ListNode *dummy, *tmp;

5 tmp = dummy = new ListNode;

6

7 while (true) {

8 int mini = INT_MAX, index = -1;

9 for (int i = 0; i < lists.size(); i++) {

10 if (lists[i] && lists[i]->val < mini) {

11 index = i;

12 mini = lists[i]->val;

13 }

14 }

15 if (index == -1) break;

16 ListNode *t = lists[index];

17 lists[index] = lists[index]->next;

18 tmp = tmp->next = t;

19 }

20 return dummy->next;

21 }

22 };

23

24 // Proper solution

25 class Solution {

26 typedef pair<int, int> pii;

27

28 public:

29 ListNode *mergeKLists(vector<ListNode *> &lists) {

30 ListNode *dummy, *tmp;

31 tmp = dummy = new ListNode;

32

33 auto cmp = [](const pii &a, const pii &b) { return a.first > b.first; };

34 priority_queue<pii, vector<pii>, decltype(cmp)> pq(cmp);

35 for (int i = 0; i < lists.size(); i++)

36 if (lists[i]) pq.push({lists[i]->val, i});

37 while (!pq.empty()) {

38 int index = pq.top().second;

39 pq.pop();

40 ListNode *t = lists[index];

41 lists[index] = lists[index]->next;

42 if (lists[index]) pq.push({lists[index]->val, index});

43 tmp = tmp->next = t;

44 }

45 return dummy->next;

46 }

47 };