题目：
给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
示例 :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明 :
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
看到这道题，我们的思路是：
1.每k个节点一组进行翻转，那就把整个链表分为num /= k个；
2.k个一组翻转，最后一组存在不够k个的情况，就按原来的排起来；
3.当这些分组都排好之后进行组装，形成一条长链。
代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null || head.next == null || k == 1){
return head;
}
ListNode p = head;
int num = 0;
while(p != null && num < k){
p = p.next;
num++;
}
num /= k; //分组
if(num == 0){
return head;
}
ListNode curr = head;
ListNode tail = curr;
for(int i = 0;i < num;i++){ //每一组进行翻转
ListNode newNode = null;
ListNode newhead = curr;
int count = k;
while(count > 0){
p = curr;
curr = curr.next;
p.next = newNode;
newNode = p;
count--;
}
if(i == 0){
head = newNode;
}else{
tail.next = newNode;
tail = newhead;
}
}
while(curr != null){ //最后的尾
tail.next = curr;
tail = tail.next;
curr = curr.next;
}
return head;
}
}
但是，循环着做着同样的事，我们可以用一种方法来实现，是什么呢？当然是递归！
代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null || head.next == null){
return head;
}
int count = 0;
ListNode curr = head;
while(count != k && curr != null){
curr = curr.next;
count++;
}
if(count == k){
curr = reverseKGroup(curr,k); //上一次翻转后的头节点
while(count -- > 0){ //翻转
ListNode tmp = head.next;
head.next = curr;
curr = head;
head = tmp;
}
head = curr;
}
return head;
}
}