题目描述

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

• 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
• 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例：

题解

反转链表利用头插法。先新建res哑节点。因为是分组反转，所以利用resIn记录此时应该在res链表进行插入的位置（也就是头插法的头）。resTail记录res的尾节点。
每组为k进行头插法：一边反转一边判断，如果发现提前结束了，需要对最后一部分再做一次翻转。

以输入：head = [1,2,3,4,5], k = 3举例

1、新建哑节点

2、前三个节点正常利用头插法插入



3、一组已经反转完成，反转下一组。此时头插法的头，应该变为resTail

4、以resIn为头，头插法插入4，5

5、此时发现，最后一组不够3个，那么现在需要做的就是再次反转resIn之后至尾节点resTail之间的节点。
还是利用头插法，resIn是头，head是resIn.next

6、插完直接返回res.next

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode res = new ListNode();
        //resTail为res链表最后的节点，resIn为res链表当前插入的位置，cur为head链表当前操作的节点
        ListNode resTail = res, resIn = res, cur = head;
        //cur==null 处理完所有节点
        while (cur != null){
        	//每k个节点一组进行反转
            for (int i = 0; i < k; i++){
            	//正常进行反转
                if (head != null){
                	//头插法把cur插入到resIn的位置
                    head = head.next;   
                    cur.next = resIn.next;
                    resIn.next = cur;
                    cur = head;
                    //记录res的结尾，每一组插入的第一个节点，为res的结尾
                    if (i == 0){
                        resTail = resIn.next;
                    }
                }else{
                	//没到k，提前结束了，已经没有节点了
                	//此时要做的就是对resIn到resTail之间的节点再进行一次反转，转回来
                    head = resIn.next;
                    cur = head;
                    resIn.next = null;
                    while (head != null){
                        head = head.next;
                        cur.next = resIn.next;
                        resIn.next = cur;
                        cur = head;
                    }
                    return res.next;
                }
            }
            //反转一组之后，更新resIn的位置
            resIn = resTail;
        }
        return res.next;
    }
}