K 个一组翻转链表

LeetCode 官方题目链接

1. 题目呈现

难度等级：🔴 困难
核心考察点：链表、递归/迭代、翻转算法

给你链表的头节点 head ，每 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]

2. 解题思路拆解

这道题是 "两两交换链表节点" 的进阶版，也是 "反转链表" 的应用版。

方法：迭代法

我们需要维护几个指针：

pre：当前要翻转的这一组节点的前一个节点。
end：当前要翻转的这一组节点的最后一个节点。
start：当前要翻转的这一组节点的第一个节点。
next：下一组节点的第一个节点（即 end.next）。

步骤：

分组检测：从 pre 开始，尝试向后走 k 步找到 end。
- 如果还没走完 k 步就遇到了 null，说明剩余节点不足 k 个，直接结束，不需要翻转。
断开连接：记录 next = end.next，然后把 end.next = null（为了调用标准的反转函数）。
局部翻转：调用反转链表函数 reverse(start)，翻转后返回新的头节点（其实就是原来的 end）。
重新连接：
- pre.next 指向翻转后的头节点。
- start 变成了这一组的尾节点，所以 start.next 连接到 next。
更新指针：pre 移动到 start，准备处理下一组。

3. 代码实现

javascript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    if (!head || k === 1) return head;

    const dummy = new ListNode(0);
    dummy.next = head;
    
    let pre = dummy;
    let end = dummy;

    while (end.next !== null) {
        // 1. 找到这一组的结尾 end
        for (let i = 0; i < k && end !== null; i++) {
            end = end.next;
        }
        
        // 如果不足 k 个，直接结束
        if (end === null) break;

        // 2. 记录相关节点
        let start = pre.next;
        let next = end.next;

        // 3. 断开链表，方便局部翻转
        end.next = null;

        // 4. 局部翻转
        pre.next = reverse(start);

        // 5. 重新连接
        start.next = next;

        // 6. 更新指针，准备下一轮
        pre = start;
        end = pre;
    }

    return dummy.next;
};

// 标准的反转链表函数
function reverse(head) {
    let prev = null;
    let curr = head;
    while (curr !== null) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

代码执行演示

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

dummy -> 1 -> 2 -> 3 -> 4 -> 5
pre = dummy, end = dummy
第 1 轮：
- end 走 2 步，指向 2。
- start = 1, next = 3。
- 断开：2.next = null。链表片段 1->2。
- 翻转 1->2 变成 2->1。返回 2。
- 连接：pre.next (dummy) -> 2。start.next (1) -> 3。
- 链表状态：dummy -> 2 -> 1 -> 3 -> 4 -> 5。
- 更新：pre = 1, end = 1。
第 2 轮：
- end (1) 走 2 步，指向 4。
- start = 3, next = 5。
- 断开：4.next = null。链表片段 3->4。
- 翻转 3->4 变成 4->3。返回 4。
- 连接：pre.next (1) -> 4。start.next (3) -> 5。
- 链表状态：dummy -> 2 -> 1 -> 4 -> 3 -> 5。
- 更新：pre = 3, end = 3。
第 3 轮：
- end (3) 尝试走 2 步。走 1 步到 5，再走 1 步 null。
- end 变为 null，跳出循环。
返回 dummy.next。

4. 复杂度分析

维度	描述
时间复杂度	$O(n)$。每个节点被遍历的次数是常数级（寻找 end 1次，翻转 1次）。
空间复杂度	$O(1)$。只用了常数个指针变量，没有使用递归栈或额外数组。

K 个一组翻转链表 ​

1. 题目呈现 ​

2. 解题思路拆解 ​

方法：迭代法 ​

3. 代码实现 ​

代码执行演示 ​