【LeetCode】HOT 100（4）网站首页 技术交流

【LeetCode】HOT 100（4）

戊子仲秋 2024-08-25 00:01:02

简介【LeetCode】HOT 100（4）

题单介绍：

精选 100 道力扣（LeetCode）上最热门的题目，适合初识算法与数据结构的新手和想要在短时间内高效提升的人，熟练掌握这 100 道题，你就已经具备了在代码世界通行的基本能力。

题单介绍：

题目：23. 合并 K 个升序链表 - 力扣（Leetcode）

题目：23. 合并 K 个升序链表 - 力扣（Leetcode）

题目的接口：

/**
 * 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) {

    }
};

解题思路：

这道困难题并不困难可真是太好了，

算是我人生中自己独自做出来的第一道困难题目了，

我打算介绍两个思路，

一个是我自己做这道题使用的思路，（他没要求复杂度，当然就可以放飞自我啦）

另一个是我在看题解的时候觉得很妙的思路，

思路一：（我的思路）

1. 直接将这个链表数组的值存进一个数组里面

2. 然后sort排序数组

3. 构建一个链表并返回即可

思路很简单，代码：

/**
 * 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) {
        vector<int> v; //将链表数组的值存进这个数组
        for(int i = 0; i < lists.size(); i++) {
            ListNode* cur = lists[i];
            while(cur) {
                v.push_back(cur->val);
                cur = cur->next;
            }
        }

        sort(v.begin(), v.end()); //排序

        ListNode* head = new ListNode; //构建链表
        ListNode* cur = head;
        head->next = nullptr;
        for(int i = 0; i < v.size(); i++) {
            ListNode* newnode = new ListNode;
            cur->next = newnode;
            cur = cur->next;
            cur->val = v[i];
        }
        cur->next = nullptr;
        return head->next;
    }
};

那么思路2：

使用优先级队列，维护一个小根堆，

不过链表的比较不能直接支持，

所以我们需要自己重载一个比较方法。

1. 将链表节点入队

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:
    class Comparator { //重载的比较方法
    public:
        bool operator()(ListNode* a, ListNode* b) {
            return a->val > b->val;
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Comparator> pq;
        for(int i = 0; i < lists.size(); i++) { //链表节点入队
            while(lists[i] != nullptr) {
                pq.push(lists[i]);
                lists[i] = lists[i]->next;
            }
        }
        ListNode* head = new ListNode; //构建链表
        ListNode* cur = head;
        while(!pq.empty()) {
            cur->next = pq.top();
            pq.pop();
            cur = cur->next;
        }
        cur->next = nullptr;
        return head->next;
    }
};