题解 | #链表中的节点每k个一组翻转#

主要思路：把多段链表反转，转化为一段一段处理

typedef struct ListNode 
{
 	int val;
	struct ListNode* next;
}ListNode;

class Solution 
{
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        if(head == NULL)	//头部为空直接返回
        {
            return head;
        }
        ListNode* p = new ListNode(0);		//哨兵节点计算链表长度
        p->next = head;
        int n = 0, re, s = 0;
        while(p->next != NULL)
        {
            p = p->next;
            n++;
        }
        if(n<k)		//如果n<K直接返回头结点
        {
            return head;
        }
        re = n/k;		//计算需要反转几次
        for(int i = 1;i<=re;i++)
        {
            head = reverseBetween(head,s+1,s+k);			//每次反转完头结点发生改变
            s = s+k;
        }
        return head;
    }
    
     ListNode* reverseBetween(ListNode* head, int m, int n)		//在链表指定区域反转
    {
        ListNode* p = new ListNode(0);		//哨兵节点
        p->next = head;
        ListNode* pre = p;
        ListNode* cur = head;
        for(int i = 1;i < m;i++)		//利用循环将pre指向需要反转节点的前面
        {
            pre = pre->next;
        }
        cur = pre->next;		//将cur指向第一个反转的节点
        for(int i = 0;i<n-m;i++)
        {
            ListNode* temp = cur->next;		//取cur后面的第一个节点
            cur->next = cur->next->next;			//断开temp节点
            temp->next = pre->next;		//将temp插入到pre的后面
            pre->next = temp;
        }
        return p->next;
    }
};