LeetCode题解之Merge k Sorted Lists 解法二

1、题目描述

2、分析

利用 vector 存储指针，同时合并k个链表。

3、代码

 1  ListNode* mergeKLists(vector<ListNode*>& lists) {
 2         
 3         vector<ListNode*> p;
 4         for (vector<ListNode*>::iterator it = lists.begin(); it != lists.end(); it++) {
 5             if (*it != NULL){
 6                 ListNode *pn = *it;
 7                 p.push_back(pn);
 8             }
 9         }
10         
11         if (p.size() == 0)
12             return NULL;
13         
14         ListNode *dummy = new ListNode(0);
15         ListNode *pn = dummy;
16         
17         while (p.size() > 0) {
18             int n = minval(p);
19             pn->next = p[n];
20             pn = pn->next;
21             p[n] = p[n]->next;
22             if (p[n] == NULL)
23                 p.erase(p.begin() + n);
24         }
25         return dummy->next;
26     }
27     
28     
29     int minval(vector<ListNode*> p)
30     {
31         auto res = p.begin();
32         for (auto it = p.begin(); it != p.end(); it++) {
33             if ((*it)->val <= (*res)->val)
34                 res = it;
35         }
36         return res - p.begin();
37     }