Leetcode 23 合并k个升序链表学习感悟

思路1：纯暴力，依次遍历依次比较偷取，不new新节点，直接拿过来

思路2：优先队列，把所有的节点入优先队列，每次吐值最小的出来串起来

//思路1： # include<iostream> # include<vector> # include<string> # include<algorithm> # include<math.h> # include<climits> # include<stack> using namespace std; struct ListNode { int val; ListNode* next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode* next) : val(x), next(next) {} }; ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode* head = NULL; head = new ListNode(-1); ListNode* p = head; int minp;//记录数值最小的节点 while (!lists.empty()) {//list非空 minp = 0; if (lists.size() == 1) { p->next = lists[0]; lists[0] = NULL; break; } for (int i = 0; i < lists.size(); i++) {//从头遍历到尾巴，找到最小的节点 if (!lists[i]) { lists.erase(lists.begin() + i); } if (i < lists.size()&&lists[i]&&(lists[minp]->val > lists[i]->val)) {//lists[i]非空 minp = i; } } if (lists[minp]) { //获取最小的节点 p->next = lists[minp]; lists[minp] = lists[minp]->next; p = p->next; p->next = NULL; } else { break; } } p = head; head = head->next; delete(p); return head; } int main(void) { vector<ListNode*> lists; lists.push_back(new ListNode(1, new ListNode(4, new ListNode(5)))); lists.push_back(new ListNode(1, new ListNode(3, new ListNode(4)))); lists.push_back(new ListNode(2, new ListNode(6))); mergeKLists(lists); system("pause"); return 0; } //思路2： # include<iostream> # include<vector> # include<string> # include<algorithm> # include<math.h> # include<climits> # include<stack> # include<queue> using namespace std; struct ListNode { int val; ListNode* next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode* next) : val(x), next(next) {} }; struct node { int val; ListNode* p; node():val(0),p(nullptr){} node(int val) :val(val), p(nullptr) {} node(int val, ListNode* p1) :val(val), p(p1) {} bool operator<(const node& b) const {//注意后面的const必须加上 return val>b.val; } }; ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<node>pq; ListNode* head=new ListNode (-1); ListNode* p; for (int i = 0; i < lists.size(); i++) { p = lists[i]; while (p) {//p存在入队 pq.push({ p->val, p });//啥写法 p = p->next; } }//所有节点入队成功 node a; p = head; while (!pq.empty()) { a = pq.top(); pq.pop(); p->next = a.p; p = p->next; } p->next = NULL; p = head; head = head->next; delete(p); return head; } int main(void) { vector<ListNode*> lists; ListNode* head; lists.push_back(new ListNode(1, new ListNode(4, new ListNode(5)))); lists.push_back(new ListNode(1, new ListNode(3, new ListNode(4)))); lists.push_back(new ListNode(2, new ListNode(6))); head=mergeKLists(lists); ListNode* p=head; while (p) { cout << p->val << " "; p = p->next; } system("pause"); return 0; }