25.K 个一组翻转链表

题目：K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例:

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明:

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group

解题思路：

对比上一题两两交换链表中的节点多了一个每k个节点为一组进行交换的条件，那么这题其实可以看成是有n个长度为k的链表进行反转然后拼接在一起。

需要注意的是根据题目n*k的长度不一定等于原链表长度，也就是说反转到最后如果剩下不足k个节点就不需要反转，同样要把没有反转的节点与已经完成反转的链表连接，说完大概思路后操作步骤如下：

首先要算出要反转的次数，后面要根据这个算出来的结果进行循环，当结果为0时就退出循环，代码如下

 let size = 0,
     cur = head;
 while (cur) {
     size++;
     cur = cur.next;
 }
 let nums = Math.floor(size / k);

设置一个虚拟头节点dummyHead指向head，同时设置一个prev，用于指向每一次反转完成后的头节点，start表示每组反转开始的位置
在反转过程中有两层循环，第一层是判断整个链表反转是否结束，第二层是判断每一组反转是否结束，那么针对第二层循环就又需要专门设置几个变量，分别为：
- count:每一组反转结束阈值，初始值为k，结束为0
- p、q:两个反转节点
- tail:每组反转后的尾部节点，反转结束后头部和尾部都会更新，那么头尾都需要与上一个和下一个进行新的连接
在开始每一组反转前先把p和tail赋值为start，q为start.next
至于为什么这么做先不急着去理解，看完反转过程就很容易明白了
首先第二层循环判断条件代码如下

while (--count) {

}

为什么是--count而不是count--或者在循环中自减呢，原因也很简单假如k为2，意思是每组只有2个节点需要反转，那么第一次--k后为1，然后完成反转，再回到循环判断--k等于0，意味着循环结束不再需要循环了

像上一题两两交换链表中的节点一样先缓存一个next,q.next=p，然后p更新为q,q更新为next

当count为0时变量位置如下图
这个时候p指向的是3，q指向的是4，所以要进行一次新的指向操作，也就是prev要指向p，tail要指向q，同时start作为每一组反转的开始节点更新为q，prev作为每组反转结束后的上一个钩子节点更新为tail，当然还有循环次数nums也需要自减1

 prev.next = p;
 start = q;
 tail.next = start;
 prev = tail;
 nums--;

重复上述步骤，当循环结束后返回dummyHead.next就是最终的结果

代码实现

let reverseKGroup = function (head, k) {
    let size = 0,
        cur = head;
    while (cur) {
        size++;
        cur = cur.next;
    }
    let dummyHead = new ListNode(-1),
        nums = Math.floor(size / k);
    dummyHead.next = head;
    let prev = dummyHead,
        start = dummyHead.next;
    while (nums) {
        let count = k,
            tail = start,
            p = start,
            q = start.next;
        while (--count) {
            let next = q.next;
            q.next = p;
            p = q;
            q = next;
        }
        prev.next = p;
        start = q;
        tail.next = start;
        prev = tail;
        nums--;
    }
    return dummyHead.next
};

# 题目：K 个一组翻转链表

# 解题思路：

# 代码实现

题目：K 个一组翻转链表

解题思路：

代码实现