LeetCode 25. K 个一组翻转链表

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

难度：困难

---

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

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

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

  示例：

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

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

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

  说明：

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

链表翻转

  首先我们需要知道单次链表翻转是如何操作的，以链表 1->2->3->null 为例：

迭代版本

  1、pre 、p 和 temp 指针指向如下：

  2、将p.next 指向 pre，pre 赋值为 p ，p 赋值为 temp，而 temp == p.next ：

  3、接下来重复步骤 2，将 p.next 指向 pre，并不断更新 pre 和 p 的指向，直到 p 为 null ，最后 pre 即为头结点。

JS 代码如下：

function ReverseList(pHead) {
    let pre = null, p = pHead;
    let temp;
    while (p) {
        temp = p.next;
        p.next = pre;
        pre = p;
        p = temp;
    }
     
    return pre;
}

递归版本

  同样，以链表 1->2->3->null 为例：

  要完成链表反转，我们需要将原先的尾节点作为新的头结点，因此递归边界是最后一个节点（head.next === null），对于遍历到的其他节点，我们需要将其下一个节点的指向反转：head.next.next = head，并将其断链，形成一条新的反向的链表：head.next = null。

  接下来，函数返回，head 指向 1，重复以上操作，完成链表反转。

JS代码：

function ReverseList(pHead) {
    const helper = head => {
        if (!head || !head.next) {
            return head;
        }
         
        let pre = helper(head.next);
        head.next.next = head;
        head.next = null;
        return pre;
    };
     
    return helper(pHead);
}

解法1：

  为了实现每 k 个节点进行一次反转，我们可以这样做：

  遍历链表，head 表示当前遍历到的节点，变量 start 记录每一段需要反转链表的起始节点，变量 count 计算当前遍历的节点个数，每当 count 为 k 时，对 start - head 的这段链表进行反转，count 恢复为 0。

  这题的反转操作不难，难点在于每次反转后节点间的断链和连接；

  假设链表 1->2->3->4->5 ，k = 2 ，1->2 段已反转完毕（2->1->3->4->5），现在需要反转 3->4 段：

  第一个断链连接操作：3->4 段中的 3 会变成该段中的尾节点，需要连接上下一段的头结点：5 ：

  第二个断链连接操作： 上一段的尾节点 1 需要和当前段的新的头结点 4 连接。

JS 代码：

var reverseKGroup = function(head, k) {
    if (k < 2) {
        return head;
    }
    
    let res, pre;
    
    // 反转 k 个节点， next 为第一个断链连接操作中的 下一段的头结点
    const flip = (head1, next, n) =>{
        let pre = next, p = head1;
        while (n--) {
            let temp = p.next;
            p.next = pre;
            pre = p;
            p = temp;
        }
    };
    
    let count = 0;
    let start;
    while (head) {
        if (count === 0) {
            start = head;  // 记录每段的起始结点
        }
        count++;
        if (count === k) { // 每当遍历了 k 个节点时
            if (pre) { // 除了第一段外，其余段需要进行第二个断链连接操作
                pre.next = head;
            }
            if (!res) {
                res = head;
            }
            pre = start;
            head = head.next;

            flip(start, head, k);
            count = 0;
        } else {
            head = head.next;
        }
    }
    
    return res;
};