目录
1.合并K个升序链表
a.核心思想
b.思路
c.步骤
2.面向对象3大特性
1.合并K个升序链表
23. 合并 K 个升序链表 - 力扣（LeetCode）https://leetcode.cn/problems/merge-k-sorted-lists/
/** * 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: // 定义比较函数，用于最小堆 struct Compare { bool operator()(const ListNode* a, const ListNode* b) { return a->val > b->val; } }; ListNode* mergeKLists(vector<ListNode*>& lists) { // 定义最小堆 std::priority_queue<ListNode*, std::vector<ListNode*>, Compare> minHeap; // 将所有链表的头节点放入堆中 for (ListNode* list : lists) { if (list != nullptr) minHeap.push(list); } // 创建哑节点 ListNode* dummy = new ListNode(); ListNode* current = dummy; // 当堆不为空时，进行合并操作 while (!minHeap.empty()) { ListNode* node = minHeap.top(); minHeap.pop(); current->next = node; current = current->next; // 如果取出的节点有下一个节点，将下一个节点放入堆中 if (node->next != nullptr) minHeap.push(node->next); } // 返回合并后的链表的头节点 return dummy->next; } };a.核心思想
利用最小堆（优先队列）来高效地依次获取多个升序链表中的最小元素，从而合并成一个升序链表。
b.思路
① 将所有链表的头节点放入最小堆中，堆按照节点的值进行排序。
② 每次从堆中取出值最小的节点，将其添加到合并后的链表中。
③ 如果取出的节点有下一个节点，将下一个节点放入堆中。
④ 重复上述步骤直到堆为空。
c.步骤
① 定义一个最小堆，用于存储链表节点，并根据节点值进行排序。
② 遍历所有链表，将每个链表的头节点放入堆中。
③ 创建一个哑节点作为合并后链表的头节点的前驱，方便操作。
④ 当堆不为空时，取出堆顶节点，将其连接到合并后的链表上。
⑤ 如果取出的节点有下一个节点，将下一个节点放入堆中。
⑥ 最后返回哑节点的下一个节点作为合并后的链表的头节点。
2.面向对象3大特性
封装 | 继承 | 多态 | |
概念 | 将数据（属性）和操作数据的方法（行为）捆绑在一起，形成一个独立的单元（即类），并尽可能隐藏对象的内部实现细节，仅通过对外提供的方法来与外界交互 | 允许一个类（子类）继承另一个类（父类）的属性和方法。子类可以复用父类的代码，同时还可以添加自己特有的属性和方法，或者重写父类的方法以实现不同的功能 | 指同一个方法调用可以根据对象的不同类型而表现出不同的行为。不同的对象对同一消息做出响应，同一操作作用于不同的对象，可以有不同的解释，产生不同的执行结果 |
作用 | 提高代码的安全性和可维护性。比如，将一个银行账户类中的余额属性设置为私有，只能通过特定的存款和取款方法进行修改，这样可以防止外部直接修改余额导致数据不合理 | 实现代码的复用和扩展。例如，定义一个动物类作为父类，有“呼吸”等方法，然后定义狗、猫等子类继承自动物类，狗类可以添加“看门”方法，猫类可以添加“抓老鼠”方法，同时都继承了“呼吸”方法 | 提高代码的灵活性和可扩展性。比如，定义一个图形类，有计算面积的方法，圆形、矩形等子类继承图形类并重写计算面积的方法，当使用图形类的引用调用计算面积方法时，根据实际对象是圆形还是矩形，会执行相应子类中的计算方法 |
希望这些内容对大家有所帮助！
感谢大家的三连支持！
