K 个一组翻转链表
25. K 个一组翻转链表
1.好理解的方法：
1 2 3 4 5 要得到 2 1 4 3 5
应该先得到 4 3 2 1 5
再得到 2 1 4 3 5
首先反转要反转的部分链表
然后根据给定的k值分组 每组的头结点和尾节点成pair存入数组中 然后反转pair数组
连接无需反转的部分（第一步反转链表后cur的位置就是要连接的头结点）
/*** 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:// 主函数：反转链表中的每k个节点ListNode* reverseKGroup(ListNode* head, int k) {// 计算链表的总长度int n = 0;ListNode* p = head;while (p) {n++; // 遍历链表，计数p = p->next;}// 如果链表长度小于 k，则不做任何反转，直接返回int mid = n % k;mid = n - mid; // mid用于确定是否有完整的k个节点可供反转// 初始化指针ListNode* pre = nullptr, * cur = head;// 反转前n个节点while (mid--) {ListNode* nxt = cur->next; // 保存当前节点的下一个节点cur->next = pre; // 反转当前节点的指针pre = cur; // 更新pre指针cur = nxt; // 更新cur指针}// 反转剩余节点return reverseList(pre, k, cur); // 将反转后的部分链表和未反转部分链表连接起来}// 辅助函数：反转链表中的指定部分ListNode* reverseList(ListNode* head, int n, ListNode* cur) {// 存储每组的起始和结束节点的pairvector<pair<ListNode*, ListNode*>> nodePair;while (head) {ListNode* l = head; // 当前组的起始节点for (int i = 0; i < n - 1; i++) {head = head->next; // 找到当前组的结束节点}ListNode* r = head; // 当前组的结束节点head = head->next; // 更新head，指向下一个组的起始节点nodePair.push_back({l, r}); // 将当前组的起始和结束节点存入pair中}// 反转每组的连接关系for (int i = nodePair.size() - 2; i >= 0; i--) {nodePair[i + 1].second->next = nodePair[i].first; // 将当前组的结束节点指向前一组的起始节点}// 连接第一个组的结束节点nodePair[0].second->next = cur; // 将第一个组的结束节点与未反转部分的起始节点连接// 返回反转后的链表头节点return nodePair[nodePair.size() - 1].first;}
};
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:ListNode* reverseKGroup(ListNode* head, int k) {if (!head || k == 1) return head; // 特殊情况处理// 计算链表长度int n = 0;ListNode* p = head;while (p) {n++;p = p->next;}// 如果链表长度不足 k，则不需要反转if (n < k) return head;// 使用 dummy 节点简化操作ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* prevGroupEnd = dummy;ListNode* cur = head;// 按组反转链表while (n >= k) {// 定义每组的起始和结束节点ListNode* groupStart = cur;ListNode* groupEnd = groupStart;for (int i = 1; i < k; i++) {groupEnd = groupEnd->next;}// 保存下一组的起始节点ListNode* nextGroupStart = groupEnd->next;// 反转当前组reverseGroup(groupStart, groupEnd);// 连接前后组prevGroupEnd->next = groupEnd;groupStart->next = nextGroupStart;// 更新指针prevGroupEnd = groupStart;cur = nextGroupStart;n -= k; // 每次减少 k 个节点}return dummy->next;}private:void reverseGroup(ListNode* start, ListNode* end) {ListNode* prev = nullptr;ListNode* curr = start;ListNode* next = nullptr;// 反转从 start 到 end 的链表while (prev != end) {next = curr->next;curr->next = prev;prev = curr;curr = next;}}
};
什么是纯虚函数？什么是抽象类？纯虚函数和抽象类在面向对象编程中的意义是什么？
纯虚函数是C++中的一种特殊函数 定义方法为： virtual void fun（int n） = 0
它只能声明，不能在定义的类中实现，因为没有实现，所以定义纯虚函数的类不能被实例化，也就是不能定义对象。也被称为抽象类。= 0 表示该函数没有定义（纯虚函数），必须在派生类中被重写。
所以抽象类就是包含了至少一个纯虚函数的类。抽象类不能被实例化，如果继承抽象类的类没有实现继承的抽象类的所有纯虚函数，那么派生类也是抽象类，也不能被实例化。
纯虚函数和抽象类在面向对象编程中的意义是什么？
提供接口定义：纯虚函数用于在基类中定义接口，派生类必须实现这些接口，以确保行为一致，这符合面向对象编程中的多态性和接口的概念。例如你有一个抽象类Shape 它包含一个虚函数draw，继承他的所有类，什么矩形、圆形，都必须主动实现这个方法，以保证每个形状都能被正确绘制。
实现多态：可以通过抽象基类的指针指向子类的对象调用子类中实现的重写方法。
避免不完整的类和强制派生类实现必要的功能：派生类想创建对象就必须实现继承的抽象类中的纯虚函数，这就保证类所有的派生类的对象都具有必要的功能。
可拓展性：通过使用抽象类和纯虚函数，能够设计出高内聚、低耦合、易于扩展的系统。你可以添加新的派生类而不影响原有代码的运行，符合开闭原则（Open/Closed Principle），即软件实体应对扩展开放，对修改封闭。
