LeetCode/LeetCode-23.cpp at master · hello-sources/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*************************************************************************
    > File Name: LeetCode-23.cpp
    > Author: ltw
    > Mail: 3245849061@qq.com
    > Created Time: Sat 16 May 2020 06:56:01 PM CST
 ************************************************************************/

#include <iostream>
using namespace std;

class Solution {
public:
    typedef pair<int, ListNode *> PIL;
    typedef pair<int, PIL> PIP;
    set<PIP> s;
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] == NULL) continue;
            s.insert(PIP(lists[i]->val, PIL(i, lists[i])));
            lists[i] = lists[i]->next;
        }
        ListNode ret, *p = &ret;
        ret.next = NULL;
        while (s.size()) {
            PIP temp = *s.begin();
            s.erase(s.begin());
            p->next = temp.second.second;
            p = p->next;
            int i = temp.second.first;
            if (lists[i] == NULL) continue;
            s.insert(PIP(lists[i]->val, PIL(i, lists[i])));
            lists[i] = lists[i]->next;
        }
        return ret.next;
    }
};