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

import java.util.*;

public class Solution {
    /**
     * @param head ListNode类
     * @param k    int整型 3
     *
     *   1    head    temp
     *   2
     *   3    temp    spiltNode
     *   
     *   4    temp     isAddList
     *   5
     *   6       
     * 
     *   7   
     *   8
     * @return ListNode类
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k == 1) {
            return head;
        }
        // 存放根据k分组好的ListNode
        List<ListNode> list = new ArrayList<>();
        // 先预存放第一个分组的节点（后面会截短）
        list.add(head);
        // 临时node节点用于遍历
        ListNode temp = head;

        // 最后一个分组是否需要反转链表
        boolean lastIsRev = false;
        // 判断需要反转链表的标志
        int i = 1;
        // 存放分割后的节点
        ListNode isAddList;
        while (temp != null && temp.next != null) {
            // 只要i % k == 0不成立  此分组就不反转，lastIsRev变量最后一个分组专用
            lastIsRev = false;
            temp = temp.next;
            i++;
            if (i % k == 0) {
                lastIsRev = true;
                i = 1;
                // spiltNode用于截断node
                ListNode spiltNode = temp;
                // temp.next 继续向下
                temp = temp.next;
                // 截断符合要求的node
                spiltNode.next = null;
                // 最后一个元素判空
                if (temp != null) {
                    //  isAddList 继续向下
                    isAddList = temp;
                    // 注意  list.add(isAddList);用于每次添加最后一个分组，当i % k == 0不成立时 正好等于最后一个分组
                    list.add(isAddList);
                }
            }
        }

	  // 反转前list.size() - 1个node
        List<ListNode> collect = new ArrayList<>();
        for (int j = 0; j < list.size() - 1; j++) {
            ListNode rev = rev(list.get(j));
            collect.add(rev);

        }
       
	   // 根据判断是否反转最后一个分组
        ListNode lastlistNode = list.get(list.size() - 1);
        if (lastIsRev) {
            ListNode rev = rev(lastlistNode);
            collect.add(rev);
        } else {
            collect.add(lastlistNode);
        }

	  // 分组重新组合成一个新的listnode
        for (int n = 0; n < collect.size() - 1; n++) {
            ListNode pre = collect.get(n);
            ListNode tail = collect.get(n + 1);

            ListNode tem = pre;
            while (tem.next != null) {
                tem = tem.next;
            }
            tem.next = tail;
        }

        return collect.get(0);
    }

     // 递归反转链表
    public ListNode rev(ListNode mid) {
        if (mid.next == null) {
            return mid;
        }
        ListNode newNode = rev(mid.next);

        ListNode temp = mid.next;
        temp.next = mid;
        mid.next = null;
        return newNode;
    }
}