K 个一组翻转链表

问题描述

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

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

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

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

还有一种变体：如果节点总数不是 k 的整数倍，那么请将最后剩余的节点翻转。

思路

解法不难想到，就是很多细节方面需要考虑，这里提供一种想起来比较简单的方法。

首先定义虚拟头节点 demmy，指向原有的头节点，避免初始情况的特殊考虑。

使用 groupPrev 指向翻转组前面的节点（已完成翻转），使用 groupNext 指向翻转组后面的节点（未完成翻转），这两个节点之间为需要翻转的节点。

如果 groupNext 为空说明所有节点已完成翻转。

初始时，groupPrev 指向 demmy，groupNext 指向第一个节点，这两个节点之间没有节点。

demmy       1           2         3          4
groupPrev   groupNext

然后 groupNext 向后移动 k 个节点，同时记录下翻转组内第一个节点 groupStart 和最后一个节点 groupEnd。

如果移动过程遇到 groupNext 为空，说明最后一组不足 k 个节点，此时最后一组的节点就是 groupStart 到 groupEnd，根据题目要求处理最后一组。

demmy       1           2         3          4
groupPrev   groupStart            groupEnd   groupNext

然后断开翻转组左右的连接（将 groupPrev 和 groupEnd 的 next 设置为空）。

demmy      | 1           2         3         | 4
groupPrev  | groupStart            groupEnd  | groupNext

调用 reverse 函数翻转组内的节点，此时 groupStart 为组内的尾节点，groupEnd 为组内头节点.

demmy      | 3         2         1           | 4
groupPrev  | groupEnd            groupStart  | groupNext

再将翻转组连接回原始链表（设置 groupPrev 和 groupStart 的 next）。

demmy       3         2         1            4
groupPrev   groupEnd            groupStart   groupNext

最后移动 groupPrev 到已完成部分的末尾，如果 groupNext 不为空，则重复上面的过程。

demmy       3         2         1           4
                                groupPrev   groupNext

代码

辅助函数 reverse(head)，将链表 head 翻转，返回新的头节点：

function reverse(head) {
    let prev = null // 需要翻转的节点之前的节点，除初始状态，不可能为空
    let curr = head // 需要翻转的节点，可能为空

    while(curr) {
        // 暂时记录下一个节点，可能为空
        const next = curr.next

        // 修改 next 指向
        curr.next = prev

        // 修改指针
        prev = curr
        curr = next
    }

    return prev
}

主函数，将链表 head k 个一组翻转：

function reverseKGroup(head, k) {

    // 虚拟头节点，指向 head 之前
    const demmy = new ListNode()
    demmy.next = head

    let groupPrev = demmy
    let groupNext = demmy.next


    // 每次循环完成一组的翻转
    while(groupNext != null) {
        // groupPrev 为翻转组第一个节点，groupNext 为翻转组最后一个节点，初始为空
        let groupStart = null, groupEnd = null

        // 组内数量
        let count = 0

        // 将至多 k 个节点放入翻转组
        while (count < k) {
            // 如果没有足够的后续节点，根据题目要求处理最后一组
            if(groupNext == null) {
                // 如果最后一组不需要翻转，直接返回最终结果
                return demmy.next

                // 如果最后一组需要翻转，退出循环，执行后面的组内翻转的代码
                // break
            }

            // 如果当前组中没有节点，在组中加入后面的节点 groupNext
            if(groupStart == null) {
                groupStart = groupEnd = groupNext
            }
            // 否则将后面的节点 groupNext 移动到组内
            else {
                groupEnd = groupNext
            }

            // 修正组后的节点
            groupNext = groupNext.next

            // 修改组内数量
            count++
        }

        // 断开分组
        groupPrev.next = null
        groupEnd.next = null
        
        // 翻转分组
        reverse(groupStart)

        // 连接分组
        groupPrev.next = groupEnd
        groupStart.next = groupNext

        // 修改指针
        groupPrev = groupStart
    }

    // 返回翻转后的链表
    return demmy.next
};