这是LeetCode里的第25道题。
题目要求：
设计思路：
使用分治法（应该可以这样说吧），不是要k个一组吗？那就把k个节点当做一小块，然后对这一小块进行倒置。然后再连接，难就是难在连接上。如下图（灵魂画师上线了！）：
如图所示，r节点就是连接处，而且此时r节点指向的是NULL，当一组交换完后，p节点指向的也是NULL，而且p节点是这一组的最后一个节点。我们要做的就是把上一组完成的尾巴r节点连接上这一组交换完后的tail节点上。这就是关键之处。当然不能忘了，当到了最后一组不满足等于k时，要记得直接返回。
解题代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverse(ListNode *head,ListNode *tail){
if(head==tail)return head;
ListNode *p=head,*r=tail;
stack<ListNode*>sl;
while(p!=r){
sl.push(p);
p=p->next;
}
while(!sl.empty()){
r->next=sl.top();
sl.pop();
r=r->next;
}
r->next=NULL;
return p;
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode *phead,*ptail,*res=NULL,*p,*r=NULL;
int i=;
phead=ptail=head;
while(ptail!=NULL){
if(i==k){
p=ptail->next;
if(res==NULL)res=reverse(phead,ptail);
else r->next=reverse(phead,ptail);
r=phead;
phead=ptail=p;
i=;continue;
}
ptail=ptail->next;
i++;
}
if(i!=){
if(r==NULL)return head;
r->next=phead;
}
return res;
}
};
最后结果：
个人总结：
这道题难度是有的，也可以同过递归来缩短代码的长度。也可以在倒置之前先统计出长度，计算出需要倒置的次数，再保存起来。最后连接。