Skip to main content

K 个一组翻转链表

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

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1： image

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

image

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

要解决这个问题，我们需要将链表每 k 个节点一组进行翻转，不足 k 个节点的部分保持原有顺序。以下是详细的解决方案：

方法思路​

  1. 递归或迭代处理：每次处理 k 个节点，递归翻转后续组，或使用迭代逐组翻转。
  2. 检查剩余节点数量：在翻转前，先检查剩余节点是否足够 k 个，不足则直接返回。
  3. 翻转当前组：使用三指针法（prev、curr、next）翻转 k 个节点，并连接前后组。
  4. 连接前后组：将前一组的尾节点连接到当前组翻转后的头节点，当前组的尾节点连接到下一组的头节点。

代码实现（迭代法）​

/**
 * 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}
 */
function reverseKGroup(head, k) {
    const dummy = new ListNode(0);
    dummy.next = head;
    let prevGroupTail = dummy; // 前一组的尾节点
    
    while (true) {
        // 检查剩余节点是否有k个
        let curr = prevGroupTail.next;
        let count = 0;
        while (curr && count < k) {
            curr = curr.next;
            count++;
        }
        if (count < k) break; // 不足k个，退出循环
        
        // 反转当前组的k个节点
        let groupPrev = null;
        curr = prevGroupTail.next;
        for (let i = 0; i < k; i++) {
            const next = curr.next;
            curr.next = groupPrev;
            groupPrev = curr;
            curr = next;
        }
        
        // 连接前后组
        const groupHead = prevGroupTail.next; // 翻转前的头节点，翻转后变为尾节点
        groupHead.next = curr; // 当前组的尾节点连接到下一组的头节点
        prevGroupTail.next = groupPrev; // 前一组的尾节点连接到当前组的头节点
        prevGroupTail = groupHead; // 更新前一组的尾节点
    }
    
    return dummy.next;
}

复杂度分析​

  • 时间复杂度：O(n)，其中 n 是链表的长度。每个节点被遍历两次（一次检查，一次翻转）。
  • 空间复杂度：O(1)，只需要常数级的额外空间。

示例验证​

输入：链表 1 → 2 → 3 → 4 → 5，k = 2
输出：链表 2 → 1 → 4 → 3 → 5

过程：

  1. 第一组（1→2）翻转：

    • 翻转后：2 → 1
    • 连接：dummy → 2 → 1，1 连接到下一组头节点 3。

  2. 第二组（3→4）翻转：

    • 翻转后：4 → 3
    • 连接：1 → 4 → 3，3 连接到下一组头节点 5。

  3. 剩余节点（5）不足 k=2，保持不变。

最终链表：dummy → 2 → 1 → 4 → 3 → 5。

关键细节说明​

  1. 虚拟头节点：统一处理头节点，避免边界条件判断。
  2. 检查剩余节点数量：确保只翻转完整的组，不足 k 个节点的部分不处理。
  3. 连接逻辑：每次翻转后，正确连接前一组的尾节点和当前组的头节点，以及当前组的尾节点和下一组的头节点。