递归实现链表k个一组反转

使用递归，时间复杂度O(n),空间复杂度O(1)

为了方便处理，创建一个在head前面的节点hair.

每次向递归方法中传入该组的头节点，头节点的上一个节点，以及个数k,然后对头节点后面的k个节点指针进行反转，首先判断是否需要反转，如果个数小于k则不需要反转，获得这个组最后一个节点的下一个节点，作为下一次递归调用的头节点，链表反转简单，三个指针pre,current,next即可。
java实现代码：

public class Solution {
  /**
   * 
   * @param head ListNode类 
   * @param k int整型 
   * @return ListNode类
   */
  public ListNode reverseKGroup (ListNode head, int k) {
      // write code here
      ListNode hair = new ListNode(0);
      hair.next = head;
      reverse(hair,head,k);
      return hair.next;
  }

  //返回该组反转后的尾节点的下一个
  public void reverse(ListNode pre,ListNode head,int k){
      int i = 0;
      ListNode pHead = head;
      while(pHead!=null&&i<k-1){
          i++;
          pHead = pHead.next;
      }
      if(i<k-1||pHead==null){
          pre.next = head;
          return;
      }
      ListNode groupNext = pHead.next;
      pre.next = pHead;
      //反转head后面的
      ListNode current = head;
      ListNode next = null;
      ListNode preNode = null;
      while(current!=null&&current!=groupNext){
          next = current.next;
          if(preNode!=null){
              current.next=preNode;
              preNode = current;
              current = next;
          }else{
              preNode = head;
              preNode.next = pHead;
              current = next;
          }
      }
      reverse(head,current,k);
  }
}