LeetCode25.k个一组翻转链表

题目来源：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/description/

题目描述：

该题目是对反转一个链表的升级版。

如何反转一个链表我在之前的博客已经写了：https://blog.****.net/qq_39241239/article/details/82973024

算法描述：

1.判断链表，若链表为空或k=1直接返回head。

2.每k个结点遍历链表。相当于把一个大链表分成k个结点为链表的小链表。

3.让每个链表都进行反转，最后再把这些链表连接起来就可以了。

代码如下：

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* p = head;  
        ListNode* r; 
        //若链表为空或k=1直接返回head
        if(!p || k == 1) 
            return p;  
        for(int i = 1; i < k; i ++){
            //若剩余结点不够k个则直接返回head
            if(!p->next)    
                return head;
            p = p->next;
        }
        //p，r为分界线，p为前面需要倒置的链表的最后一个结点，r为进入递归的第一个节点（head）
        r = p->next;
        //截取链表
        p->next = NULL;
        //temp为倒置后的链表
        ListNode* temp = reverse(head);
        ListNode* newHead = temp;
        //找到链表最后
        while(temp->next){
            temp= temp->next;
        }
        //在链表最后递归拼接需要倒置的其他链表
        temp->next = reverseKGroup(r,k);
        return newHead;
    }
    //反转链表方法
    ListNode* reverse(ListNode* head) {
        ListNode *p,*newHead=NULL;
       	while(head){
       		p=head;
       		head=head->next;
       		p->next=newHead;
       		newHead=p;
		}
        return newHead;
    }
};