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

import java.util.*;

/*
 * 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

        //为空返回null
        if(head==null){
            return null;
        }

        //只有一个元素直接返回
        if(head.next==null){
            return head;
        }

        //k为1说明不需翻转 直接返回
        if(k==1){
            return head;
        }
        //记录head
        ListNode start = head;
        
        //得出链表长度
        int size = 0;
        while (start != null) {
            start = start.next;
            size++;
        }

        //k大于长度不合理 直接返回原链表
        if(k>size){
            return head;
        }
        //此时恢复start指向
        start = head;
        
        //使head指向第一组元素最后一个元素
        //此时指向后 最后可以直接使用head返回
        //原链表已用start指向 所以原链表的数据不会丢失
        int n = k;
        while (n > 1) {
            head = head.next;
            n--;
        }

        ListNode tmp;
        tmp=head;
        n = k;
        //判断有多少组可以翻转
        int num = size / k;

        //用一个新结点指向start
        ListNode h = start;
        
        for (int i = 1; i <= num; i++) {

            //使h指向n个元素之后的元素 记录下此时的值
            while (n >= 1) {
                h = h.next;
                n--;
            }
            n = k;

            //进行翻转 并将反转后那一组的头结点进行返回
            ListNode ret = revers(start, k);
            
            //第一组翻转的数据不需连接
            //并且此时第一组翻转的第一个元素为原第一组最后一个元素
            //第二组之后的都需要与前面的组链接
            if (i != 1) {

                //tmp记录下了head 此操作得到新链表的末尾结点
                while (tmp.next!=null) {
                    tmp=tmp.next;
                 
                }
                //将末尾结点的next指向翻转的一组
                tmp.next = ret;

                //使start指向原链表的k个元素之后的元素
                start = h;
                
            }
        
        //使start指向原链表的k个元素之后的元素
        start = h;
        }

        //连接上最后的元素
        while(tmp.next!=null){
            tmp=tmp.next;
        }
        tmp.next=h ;
        return head;
    }
    public static ListNode revers(ListNode head, int k) {
        ListNode cur = head.next;
        ListNode curNext = cur.next;
        head.next = null;
        while (k > 1) {
            curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
            k--;
        }
        return head;
    }
}