题解 | #链表中的节点每k个一组翻转#

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        //特殊值处理，空链表，或者链表的长度为1,或者是链表反转区间长度为1
        if(head == null || head.next == null || k==1){
            return head;
        }
        ListNode head0 = head;//临时头指针
        int size = 0;  //链表的长度
        while (head0!=null){//遍历链表，统计链表的长度
            head0 = head0.next;
            size++;
        }
        head0 = head;//临时头指针重新指向头指针
        int count = size/k;//反转区间的个数
        if(count<1){//如果反转区间的个数为0，即不用反转
            return head;
        }
        ListNode tail = null;  //当前反转区间的尾节点
        ListNode prep = null;  //当前节点的前驱节点
        for(int i=0;i<count;i++){
            ListNode next = head0.next;  //当前节点的后继节点
            ListNode head0Temp = head0; //反转区间的开始节点
            int len = k;
            while (len>0){//null->1->2
                next = head0.next;  //当前节点的后继节点
                head0.next = prep;  //链表反转
                prep = head0;  //前驱节点后移
                head0 = next;  //当前节点后移
                len--;  //反转区间减一
            }
            if(i==0){//如果是第一个反转区间，则prep为反转后的头指针
                head = prep;
            }else{
                tail.next = prep; //前一反转区间的尾指针指向当前反转区间的头指针
            }
            tail = head0Temp;  //更新当前反转区间的尾节点
            prep = tail;  //更新反转区间的前驱节点
            prep.next = head0;//当前反转区间的尾节点指向下一个反转区间的头节点
        }
//         if(size%k != 0){//剩下的节点不足以分成一组，前一反转区间的尾指针指向剩下的头节点节点
//             tail.next = head0;
//         }
        return head;
    }
}