25. Reverse Nodes in k-Group

5/5/2018 update:

12/21/2017 update
A better and more concise approach. Two points need to keep in mind.
1.  the newHead needs to be stored before adjust the list.
2. counter location is no longer accurate after reversing.

 /**  
  * 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) {  
     ListNode dummy = new ListNode(0);  
     ListNode counter = head;  
     dummy.next = head;  
     head = dummy;  
     int count = 0;  
     while (counter != null) {  
       count ++;  
       if (count % k == 0) {  
         // reverse  
         ListNode prev = head.next;  
         ListNode cur = head.next.next;  
         for (int i = 0; i < k - 1; i++) {  
           ListNode temp = cur.next;   
           cur.next = prev;   
           prev = cur;   
           cur = temp;             
         }  
         ListNode newHead = head.next;  
         head.next.next = cur;   
         head.next = prev;  
         head = newHead;  
         counter = cur;  
       } else {  
         counter = counter.next;    
       }  
     }  
     return dummy.next;  
   }  
 }  

}
-------------------------------------------------------------------

思路：
和reverse linked list II相似。相当于每次以n为窗口向后reserve。

实现：
九章课上讲的是答案中的第一种解法，太容易出错了，太多额外node,容易晕。精简代码如下（九章答案version 2）：
要注意的是reverse需要返回n1， 在reverse之前保存下来。

 public class Solution {  
   /*  
    * @param head: a ListNode  
    * @param k: An integer  
    * @return: a ListNode  
    */  
   public ListNode reverseKGroup(ListNode head, int k) {  
     // write your code here  
     // create dummy  
     ListNode dummy = new ListNode(0);  
     dummy.next = head;  
     head = dummy;  
     while(head!=null) {  
       head = reverseNextK(head, k);  
     }  
     //reverse  
     return dummy.next;  
   }  
   // head-> n1->n2->....nk->nk+1  
   // => head-> nk->nk-1->....->n1->nk+1  
   private ListNode reverseNextK(ListNode head, int k) {  
     // check valid  
     ListNode c = head;  
     for(int i=0 ;i < k; i++) {  
       c = c.next;  
       if(c == null)  
         return null;  
     }  
     ListNode prev = head.next;  
     ListNode n1 = head.next;  
     ListNode cur = prev.next;  
     for(int i = 0; i < k-1; i++) {  
       ListNode temp = cur.next;  
       cur.next = prev;  
       prev = cur;  
       cur = temp;  
     }  
     head.next.next = cur;  
     head.next = prev;  
     return n1;  
   }  
 }