K 个一组翻转链表

题目

题目来源：力扣（LeetCode）

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

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

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

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

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

思路分析

1、首先，我们创建一个虚拟头节点 hair，并将虚拟头节点指向链表的头节点。
2、然后，定义一个 pre 指针指向虚拟头节点，定义一个 tail 指针指向 pre 指针指向的节点
3、tail 指针每次向后移动一步，直到找到第 K 个节点，例如我们这里的 K 是 3，此时 tail 指针指向节点 3
4、此时我们找到了第一组 K 个节点的链表，我们先对这一组链表进行反转
5、定义一个 prev 指针 指向 tail 指针所指节点的下一个节点，定义一个 P 指针指向 head 节点，并定义一个 next 指针指向 P 指针所指向节点的下一个节点
6、将 P 指针所指向的节点的 next 指针域指向 prev 指针所指向的节点
7、将 prev 指针移动到 P 指针所指向的节点
8、将 P 指针移动到 next 指针所指向的节点上
9、然后将 next 指针继续往后移动，指向 P 指针所指向节点的下一个节点
10、继续将 prev 指针、P 指针、next 指针 往后移动，当 prev 指针与 tail 指针指向同一节点的时候，我们的 K 个一组链表翻转完了
此时翻转完后的链表如下：
11、第一个 K 个一组的链表翻转完后，继续往后寻找下一组需要翻转的链表。将 pre 指针移动到 head 指针所指向的节点，让 pre 指针所指向的节点称为下一组待翻转链表的前驱节点，然后将 head 指针移动到 pre 指针所指向节点的下一个节点，让 head 指针所指向的节点称为下一组待翻转链表的头节点，同时把 tail 指针指向 pre 指针所指向的节点
12、然后 tail 节点继续往后移动 K 步，如果 tail 指针不为null，则继续翻转这一组链表，如果 tail 指针为 null，证明后面的节点已不足 K 个，返回链表，不再翻转后面的节点

const myReverse = (head, tail) => {
    let prev = tail.next;
    let p = head;
    while (prev !== tail) {
        const nex = p.next;
        p.next = prev;
        prev = p;
        p = nex;
    }
    return [tail, head];
}
var reverseKGroup = function(head, k) {
    // 创建一个虚拟头节点
    const hair = new ListNode(0);
      // 将 虚拟头节点指向链表的头节点
    hair.next = head;
      // 定义 pre 指针，指向头节点
    let pre = hair;
    while (head) {
          // 定义 tail 指针，指向 pre 指针所指向的节点
        let tail = pre;
        // 查看剩余部分长度是否大于等于 k
        for (let i = 0; i < k; ++i) {
            tail = tail.next;
            if (!tail) {
                return hair.next;
            }
        }
        const nex = tail.next;
        [head, tail] = myReverse(head, tail);
        // 把子链表重新接回原链表
        pre.next = head;
        tail.next = nex;
        pre = tail;
        head = tail.next;
    }
    return hair.next;
};