LeetCode hard也就这么回事

简介: LeetCode hard也就这么回事

给你一个链表数组,每个链表都已经按升序排列。


请你将所有链表合并到一个升序链表中,返回合并后的链表。


示例 1:


输入:lists = [[1,4,5],[1,3,4],[2,6]]

输出:[1,1,2,3,4,4,5,6]

解释:链表数组如下:

[1->4->5,1->3->4,2->6]

将它们合并到一个有序链表中得到。

1->1->2->3->4->4->5->6

       老样子,先贴我的图,可以说是又快又好,不过这里原题给的是子链表有序(常规写法也能写,不难),如果子链表无序,那各位读者应该是焦头烂额+汗流浃背了

         这个题,其实看完我上一篇分享可以立马写出来了,链表排序?看完你也能手撕

思路还是一样,先转换成数组存放,再排序,再存回链表中(思路很简单)

 

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<int> s;  // 存储所有链表节点的值的容器
 
        // 遍历所有链表,将节点的值依次放入容器中
        for (int i = 0; i < lists.size(); i++) {
            ListNode* cur = lists[i]; // 当前链表的头节点
            while (cur != nullptr) {
                s.push_back(cur->val); // 将节点值加入容器
                cur = cur->next; // 指针移动到下一个节点
            }
        }
        
        sort(s.begin(),s.end()); // 将容器中的值进行排序(升序)
        
        ListNode *tt = new ListNode(-1); // 创建一个哑节点 tt,用于构建结果链表
        ListNode *res = tt; // 使用 res 保存结果链表的头节点
        int i = 0; // 用于遍历排序后的容器 s
        
        // 遍历列表
        for (int j = 0; j < lists.size(); j++) {       
            ListNode* cur1 = lists[j]; // 当前链表的头节点
            while(cur1 != nullptr) {
                cur1->val = s[i++]; // 将排序后的值赋给当前节点
                tt->next = cur1; // 连接当前节点到结果链表
                tt = cur1; // tt 指针移动到当前节点
                cur1 = cur1->next; // cur1 指针移动到下一个节点
            }
        }
        
        return res->next; // 返回结果链表的头节点
    }
};
 

以下是LeetCode官方的各种题解,为大家添加上了注释

方法一:顺序合并

我们可以想到一种最朴素的方法:用一个变量 ans 来维护以及合并的链表,第 i次循环把第 i 个链表和 ans 合并,答案保存到 ans 中。

class Solution {
public:
    // 合并两个有序链表
    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
        // 如果其中一个链表为空,则直接返回另一个链表
        if ((!a) || (!b)) return a ? a : b;
        
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                // 当a链表的值小于b链表的值时,将a链表的节点拼接到结果链表后面,并更新a链表的指针
                tail->next = aPtr; aPtr = aPtr->next;
            } else {
                // 当a链表的值大于等于b链表的值时,将b链表的节点拼接到结果链表后面,并更新b链表的指针
                tail->next = bPtr; bPtr = bPtr->next;
            }
            // 更新结果链表的尾指针
            tail = tail->next;
        }
        // 将剩下的未合并的链表直接拼接到结果链表的尾部
        tail->next = (aPtr ? aPtr : bPtr);
        
        // 返回结果链表
        return head.next;
    }
 
    // 合并K个有序链表
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans = nullptr;
        for (size_t i = 0; i < lists.size(); ++i) {
            // 逐个合并链表,将结果保存到ans中
            ans = mergeTwoLists(ans, lists[i]);
        }
        // 返回最终的合并结果
        return ans;
    }
};

方法二:分治合并

考虑优化方法一,用分治的方法进行合并。

class Solution {
public:
    // 合并两个有序链表
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a) || (!b)) return a ? a : b; // 如果其中一个链表为空,则直接返回另一个链表
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) { // 比较两个节点的值,将较小的节点接入结果链表
                tail->next = aPtr; 
                aPtr = aPtr->next; // 更新a链表指针
            } else {
                tail->next = bPtr; 
                bPtr = bPtr->next; // 更新b链表指针
            }
            tail = tail->next; // 更新结果链表的尾节点
        }
        tail->next = (aPtr ? aPtr : bPtr); // 将剩余未合并完成的节点接入结果链表
        return head.next; // 返回结果链表的头节点
    }
 
    // 递归合并多个有序链表
    ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l]; // 当l和r相等时,表示只有一个链表,直接返回该链表
        if (l > r) return nullptr; // 当l大于r时,表示没有待合并的链表,返回空指针
        int mid = (l + r) >> 1; // 计算中间位置
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r)); // 递归合并左右两个部分
    }
 
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1); // 调用递归函数,合并整个链表数组
    }
};

方法三:使用优先队列合并


这个方法和前两种方法的思路有所不同,我们需要维护当前每个链表没有被合并的元素的最前面一个,k 个链表就最多有 k 个满足这样条件的元素,每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候,我们可以用优先队列来优化这个过程。

class Solution {
public:
    // 定义结构体Status,用于在优先队列中存储节点信息
    struct Status {
        int val; // 节点的值
        ListNode *ptr; // 节点指针
        bool operator < (const Status &rhs) const {
            return val > rhs.val; // 优先队列按照节点值的大小进行排序
        }
    };
 
    priority_queue<Status> q; // 创建优先队列q,按照节点值的大小进行排序
 
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 将每个链表的第一个节点放入优先队列
        for (auto node : lists) {
            if (node)
                q.push({node->val, node});
        }
 
        ListNode head, *tail = &head; // 创建结果链表的头节点head和尾节点tail
        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; // 返回结果链表的头节点
    }
};
相关文章
|
5月前
|
算法 Java C语言
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
35 1
|
5月前
|
算法 数据挖掘 Python
LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】
LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】
|
6月前
[leetcode~数位动态规划] 2719. 统计整数数目 hard
[leetcode~数位动态规划] 2719. 统计整数数目 hard
|
6月前
LeetCode链表hard 有思路?但写不出来?
LeetCode链表hard 有思路?但写不出来?
|
6月前
|
机器学习/深度学习 索引
字节3面真题,LeetCode上hard难度,极具启发性题解
字节3面真题,LeetCode上hard难度,极具启发性题解
【每日一题】leetcode hard难度:二叉树最大路径和
【每日一题】leetcode hard难度:二叉树最大路径和
【每日一题】leetcode hard难度:二叉树最大路径和
LeetCode:4_Median of Two Sorted Arrays | 求两个排序数组的中位数 | Hard
题目: There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Subscribe to see which companies asked this question 解题思路:   我自己想的方法,先排序在查找。
1191 0
LeetCode:145_Binary Tree Postorder Traversal | 二叉树后序遍历 | Hard
题目:Binary Tree Postorder Traversal 二叉树的后序遍历,题目要求是采用非递归的方式,这个在上数据结构的课时已经很清楚了,二叉树的非递归遍历不管采用何种方式,都需要用到栈结构作为中转,代码很简单,见下: 1 struct TreeNode { 2 ...
790 0