25.K个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

思路详解：

1. 定义虚拟头节点，定义左右边界指针，让他们一开始指向虚拟头节点

2. 开始移动右边界的指针，移动k步停下，判断右边界指针是否为空，如果不为空就反转，为空跳出循环 

3. 记录左指针的下一个节点和右指针的下一个节点，前者是翻转链表的尾节点，后者是下一组链表的头节点，方便连接

4. 翻转：这里使用三指针法翻转链表 如果忘了如何翻转链表请看->实习冲刺第二天-CSDN博客

5. 翻转后重新连接头尾节点，更新左右指针的位置，最后返回虚拟头节点的下一个节点即可

代码详解：

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
       ListNode*dummy=new ListNode(0);//虚拟头节点
       dummy->next=head;//连接

       ListNode*left=dummy,*right=dummy;//左右边界指针，开始的时候全部指向虚拟头节点

       while(true)
       {
        for(int i=0;i<k&&right!=nullptr;i++)right=right->next;//移动右边界指针
        if(right==nullptr)break;//如果右边界指针为空不能继续移动了直接跳出循环

        ListNode*leftNext=left->next;//反转后的尾节点
        ListNode*rightNext=right->next;//下一组链表的头节点

        right->next=nullptr;//断开已经分好组的链表
        left->next=reverse(left->next);//将头节点重新连接
        leftNext->next=rightNext;//尾节点重新连接
        left=right=leftNext;//更新左右节点的位置
       } 
       return dummy->next;//返回新链表的头节点即可
    }
    ListNode*reverse(ListNode*head)//反转链表函数
    {
        ListNode*cur=head;
        ListNode*pre=nullptr;
        while(cur)
        {
            ListNode*next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};

 面经：

1. 什么是纯虚函数，抽象类，他们在面向对象编程中有什么优势

    纯虚函数：virtual 返回值 函数名 （参数）=0

   当类中存有纯虚函数时变成抽象类：

   抽象类不能被实例化即无法创建对象

   子类必须重写抽象类的纯虚函数才能实例化对象不然仍为抽象类

   由于不能实例化抽象类一般作为基类

#include<iostream>
using namespace std;

class base
{
public:
        virtual void fun() = 0;
};

class son:public base
{
public:
        virtual void fun()
        {
                cout << "重写fun";
        }
};

int main()

{
        base* b = new son;
        b->fun();
        delete b;
}