当前位置：首页 > ds >正文

LeetCode 刷题【23. 合并 K 个升序链表】

ds 2025/8/3 12:50:51

23. 合并 K 个升序链表

自己做

归并实现1：两两归并

/*** Definition for singly-linked list.* 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) {}* };*/
class Solution {
public:ListNode* getMerge(ListNode* list1, ListNode* list2){           //两有序链表合并ListNode *p = list1, *q = list2;ListNode *res = new ListNode();ListNode *k = res;while(p != nullptr && q != nullptr){                    //合并两有序if(p->val < q->val){                                //p指向的更小k->next = p;p = p->next;}else{                                                //q指向的更小k->next = q;q = q->next;}k = k->next;                                        //k指向尾部k->next = nullptr;}while(p != nullptr){                                //p没有遍历完k->next = p;p = nullptr;}while(q != nullptr){                                //q没有遍历完k->next = q;q = nullptr;}return res->next;}ListNode* mergeKLists(vector<ListNode*>& lists) {int len = lists.size();                 //有多少个链表if(len == 0)                            //空链表不处理     return nullptr;if(len == 1)                            //只有一个链表，直接返回return lists[0];while(len > 1){lists[1] = getMerge(lists[0],lists[1]); //两个有序链表合并为一个lists.erase(lists.begin());len = lists.size();                     //合并后链表数组的长度更新}return lists[0];}
};

归并实现2：从上往下扫描

/*** Definition for singly-linked list.* 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) {}* };*/
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {int len = lists.size();                 //有多少个链表ListNode* res = new ListNode();ListNode* k = res;//首先消除所有的空链表for (vector<ListNode*>::iterator it = lists.begin(); it != lists.end(); ) {   //从上往下扫描if ((*it) == nullptr) {        //it所指向的空间存放的链表为空it = lists.erase(it);            //消除}elseit++;}len = lists.size();         //更新长度if (len == 0)                        //空链表数组直接返回return nullptr;while (len > 1) {                     //只要是大于两个链表就一直扫描int q = 0;                      //最小值所指向的p索引下标int min = lists[0]->val;            //设置当轮的最小值for (int i = 0; i < len; i++) {   //从上往下扫描if (lists[i]->val < min) {min = lists[i]->val;q = i;}}//扫描结束找到当轮的最小值k->next = lists[q];lists[q] = lists[q]->next;k = k->next;k->next = nullptr;if (lists[q] == nullptr) {        //lists[q]所指向的链表已经完全取完//删除该位置的指针vector<ListNode*>::iterator it = lists.begin();for (int i = 0; i < q; i++)it++;lists.erase(it);//更新长度len = lists.size();}}//此时只剩下一个链表lists[0]k->next = lists[0];return res->next;}
};

看题解

优先队列

class Solution {
public:struct Status {int val;ListNode *ptr;bool operator < (const Status &rhs) const {return val > rhs.val;}};priority_queue <Status> q;ListNode* mergeKLists(vector<ListNode*>& lists) {for (auto node: lists) {if (node) q.push({node->val, node});}ListNode head, *tail = &head;while (!q.empty()) {auto f = q.top(); q.pop();tail->next = f.ptr; tail = tail->next;if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});}return head.next;}
};