目录
1.排序链表
a.核心思想
b.思路
c.步骤
2.虚函数指针是什么时候初始化的
1.排序链表
148. 排序链表 - 力扣（LeetCode）https://leetcode.cn/problems/sort-list/
/** * 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* sortList(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; // 找到中点 ListNode* slow = head; ListNode* fast = head->next; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; } ListNode* mid = slow->next; slow->next = nullptr; // 递归排序左右子链表 ListNode* left = sortList(head); ListNode* right = sortList(mid); // 合并两个有序链表 return merge(left, right); } ListNode* merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail = &dummy; while (l1 != nullptr && l2 != nullptr) { if (l1->val < l2->val) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = (l1 != nullptr) ? l1 : l2; return dummy.next; } };a.核心思想
利用归并排序的思想对链表进行排序，归并排序适合链表的排序，因为其合并过程只需要改变节点的指针指向，而不需要像数组那样进行大量的数据移动。
b.思路
① 分解：找到链表的中点，将链表分成两个子链表。
②递归排序：对两个子链表分别进行递归排序。
③ 合并：将两个排好序的子链表合并成一个有序的链表。
c.步骤
① 找到中点：使用快慢指针法，快指针每次走两步，慢指针每次走一步，当快指针到达链表末尾时，慢指针指向的就是中点。
②递归终止条件：当链表为空或只有一个节点时，直接返回该链表。
③ 合并链表：创建一个虚拟头节点，然后比较两个子链表的节点值，将较小的节点连接到新链表上，直到其中一个子链表为空，然后将另一个子链表直接连接到新链表末尾。
2.虚函数指针是什么时候初始化的
① 基类构造阶段：调用基类构造函数时，vptr指向基类的虚函数表（vtable）。
② 派生类构造阶段：调用派生类构造函数时，vptr被更新为指向派生类的vtable。
③ 析构阶段：析构时逆向更新，先析构派生类（vptr指向派生类vtable），再析构基类（vptr指向基类vtable）。
希望这些内容对大家有所帮助！
感谢大家的三连支持！
