c++-c++编程基础之leetcode题解第23题合并K个升序链表.zip资源-CSDN下载

共1个文件

md：1个

需积分: 50 6 浏览量 2024-04-07 05:24:17 上传评论收藏 2KB ZIP 举报

在C++编程中，LeetCode是一个非常受欢迎的在线平台，用于练习和提升编程技能，特别是算法和数据结构。第23题是关于合并K个升序链表的问题，这是一个典型的链表操作题目，旨在考察程序员对链表操作的熟练程度以及解决复杂问题的能力。在这个问题中，我们需要将K个已经按升序排序的链表合并成一个单一的升序链表。我们来理解一下链表的基本概念。链表是一种线性数据结构，它的元素（节点）不是在内存中连续存储的，每个节点包含数据和指向下一个节点的指针。在C++中，链表通常通过结构体或类来实现，比如定义一个`struct ListNode`，包含一个整型数据和一个指向下一个节点的`ListNode*`指针。对于第23题，我们需要设计一个高效的算法来合并这些链表。一种常见的方法是使用优先队列（最小堆）。将所有链表的头节点放入优先队列中，队列的排序规则是节点的值越小，优先级越高。每次从队列中取出最小的节点，将其与新节点连接，并将新节点的下一个指针指向队列中下一个最小的节点，直到队列为空，合并完成。在C++中，我们可以使用STL中的`priority_queue`来实现这个数据结构。定义一个比较函数对象，用于比较两个链表节点的值，然后创建一个优先队列并插入所有链表的头节点。在合并过程中，不断从队列中取出最小节点，构建新的链表。 ```cpp struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; bool compare(ListNode* a, ListNode* b) { return a->val < b->val; } ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> pq(compare); for (ListNode* node : lists) { if (node) { pq.push(node); } } ListNode dummy(0); ListNode* current = &dummy; while (!pq.empty()) { ListNode* minNode = pq.top(); pq.pop(); current->next = minNode; current = current->next; if (minNode->next) { pq.push(minNode->next); } } return dummy.next; } ``` 在这个代码片段中，`mergeKLists`函数接收一个链表头节点的向量，并返回合并后的链表头节点。`compare`函数用于比较节点的值。`dummy`是一个临时的头节点，用来初始化新链表，`current`则用于遍历新链表并连接节点。此外，还需要考虑内存管理。在C++中，手动管理内存是非常重要的。当链表不再需要时，应该释放所占内存。对于这个问题，由于我们没有直接创建链表节点，因此在合并完成后，原始的链表节点仍然由原链表持有，不需要特别处理。但如果是自定义创建的链表，记得在适当的时候使用`delete`释放节点。解题第23题的过程涉及到C++中的链表操作、优先队列、比较函数对象以及动态规划的思维。这样的题目不仅可以提高C++编程技巧，还能加深对数据结构和算法的理解。通过不断练习LeetCode上的问题，可以有效提升程序员的编程能力。

资源推荐

资源详情

资源评论

收起资源包目录

c++_c++编程基础之leetcode题解第23题合并K个升序链表.zip （1个子文件）

c++_c++编程基础之leetcode题解第23题合并K个升序链表

README.md 4KB

# [23. Merge k Sorted Lists (Hard)](https://leetcode.com/problems/merge-k-sorted-lists/) You are given an array of <code>k</code> linked-lists <code>lists</code>, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.   Example 1: <pre>Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6 </pre> Example 2: <pre>Input: lists = [] Output: [] </pre> Example 3: <pre>Input: lists = [[]] Output: [] </pre>   Constraints: <ul> <li><code>k == lists.length</code></li> <li><code>0 <= k <= 10^4</code></li> <li><code>0 <= lists[i].length <= 500</code></li> <li><code>-10^4 <= lists[i][j] <= 10^4</code></li> <li><code>lists[i]</code> is sorted in ascending order.</li> <li>The sum of <code>lists[i].length</code> won't exceed <code>10^4</code>.</li> </ul> **Companies**: [Facebook](https://leetcode.com/company/facebook), [Amazon](https://leetcode.com/company/amazon), [Microsoft](https://leetcode.com/company/microsoft), [Google](https://leetcode.com/company/google), [ByteDance](https://leetcode.com/company/bytedance), [Yandex](https://leetcode.com/company/yandex), [Apple](https://leetcode.com/company/apple), [Adobe](https://leetcode.com/company/adobe), [VMware](https://leetcode.com/company/vmware), [Bloomberg](https://leetcode.com/company/bloomberg), [eBay](https://leetcode.com/company/ebay), [tiktok](https://leetcode.com/company/tiktok), [Indeed](https://leetcode.com/company/indeed), [Oracle](https://leetcode.com/company/oracle), [Walmart Labs](https://leetcode.com/company/walmart-labs), [Qualtrics](https://leetcode.com/company/qualtrics), [Sprinklr](https://leetcode.com/company/sprinklr), [Cruise Automation](https://leetcode.com/company/cruise-automation) **Related Topics**: [Linked List](https://leetcode.com/tag/linked-list/), [Divide and Conquer](https://leetcode.com/tag/divide-and-conquer/), [Heap (Priority Queue)](https://leetcode.com/tag/heap-priority-queue/), [Merge Sort](https://leetcode.com/tag/merge-sort/) **Similar Questions**: * [Merge Two Sorted Lists (Easy)](https://leetcode.com/problems/merge-two-sorted-lists/) * [Ugly Number II (Medium)](https://leetcode.com/problems/ugly-number-ii/) ## Solution 1. Heap ```cpp // OJ: https://leetcode.com/problems/merge-k-sorted-lists/ // Author: github.com/lzl124631x // Time: O(NlogK) // Space: O(K) class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode dummy, *tail = &dummy; auto cmp = [](auto a, auto b) { return a->val > b->val; }; priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q(cmp); for (auto list : lists) { if (list) q.push(list); // avoid pushing NULL list. } while (q.size()) { auto node = q.top(); q.pop(); if (node->next) q.push(node->next); tail->next = node; tail = node; } return dummy.next; } }; ``` ## Solution 2. Divide And Conquer (Merge Sort) ```cpp // OJ: https://leetcode.com/problems/merge-k-sorted-lists/ // Author: github.com/lzl124631x // Time: O(NlogK) // Space: O(1) class Solution { private: ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode head, *tail = &head; while (a && b) { if (a->val < b->val) { tail->next = a; a = a->next; } else { tail->next = b; b = b->next; } tail = tail->next; } tail->next = a ? a : b; return head.next; } public: ListNode* mergeKLists(vector<ListNode*>& lists) { if (lists.empty()) return nullptr; for (int N = lists.size(); N > 1; N = (N + 1) / 2) { for (int i = 0; i < N / 2; ++i) { lists[i] = mergeTwoLists(lists[i], lists[N - 1 - i]); } } return lists[0]; } }; ```

评论收藏

内容反馈