前言

这是一道看似简单，但又是细节搞死人的题目。

题目链接:K 个一组翻转链表

思路

该题如果用 栈或递归来做，那必定是一个简单的问题了，其重点在于题目要求使用常数级的额外空间。

1. 首先获取链表的长度 length

2. 关于K值，当 其 k == 1 或者 k > length 情况，显然都无需翻转

3. 定义一个 cur,last 分别指向当前节点，以及上个节点，pref 指向的是上个k链中的最后一个节点.startNode指向的是每个k链原排序中的第一个节点。

4. 当前节点不为 k 链中最后一个节点时，将当前节点的next指向 last 节点，实现 k 链内的翻转

5. 当前节点为 K 链中最后一个节点时

   (1)将当前节点的next 指向last 节点. 该节点也是 k 链的头部，因此将 上个K链中的最后一个节点 pref.next = cur;（如果pref==null.说明此时处于第一个 k链，当前节点即是 Head节点）。

   (2)更新 pref 指向该k链中最后一个节点，即是startNode.

   (3)在 下个k链的头部节点未确定下，pref.next 先指向接下来的第一个节点。目的是防止接下的不满足k个情况而导致其头部没有前缀

   (4)startNode 则更新指向下个未翻转k链的第一个节点。

代码

public ListNode reverseKGroup(ListNode head, int k) {
        ListNode pref = null;
        ListNode cur,last, startNode,t;
        int length = getLength(head);
        int endIndex = length - length%k -1;
        if (k == 1 || k > length) return head;
        int i = 0;
        cur = head;
        startNode = head;
        last = null;
        while (cur != null) {
            if (i > endIndex){
                break;
            }
            //末尾
            if (i % k == k - 1) {
                t = cur.next;
                if (pref == null) {//说明是首部
                    head = cur;//当前作为head
                } else {
                    pref.next = cur;
                }
                cur.next = last;//访问上次
                cur = t;
                pref = startNode;// 上一轮的开始节点，也是上一轮的尾部，其变为了下个k长链表的前缀
                pref.next = cur;// 将其指向为变化的下个k链表的头部，目的是防止接下的不满足k个情况而导致其头部没有前缀
                startNode = cur;//新一轮k
            } else {
                t = cur.next;
                cur.next = last;
                last = cur;
                cur = t;
            }
            i++;
        }
        return head;
}
public int getLength(ListNode head){
    int size = 0 ;
    while (head!=null){
        head= head.next;
        size++;
    }
    return size;
}