K个一组翻转链表：算法解析与实现指南

翻转链表是算法面试中常见的问题之一。K 个一组翻转链表是翻转链表的变种，要求每 K 个节点为一组进行翻转，如果剩余节点不足 K 个，则保持原有顺序。我们可以通过递归或迭代的方式来解决这个问题。

问题描述

给定一个链表，每 K 个节点一组进行翻转，返回翻转后的链表。如果节点总数不是 K 的整数倍，则最后剩余的节点保持原有顺序。

示例

输入：1->2->3->4->5, K = 2
输出：2->1->4->3->5

输入：1->2->3->4->5, K = 3
输出：3->2->1->4->5

解决方案

我们可以使用递归或迭代的方法来解决这个问题。以下是使用迭代的方法：

1. 迭代法

迭代法的思路是：

• 遍历链表，每次找到 K 个节点。
• 翻转这 K 个节点。
• 将翻转后的子链表连接到结果链表中。
• 继续遍历剩余的链表，直到链表结束。

function reverseKGroup(head, k) {
    // 辅助函数：翻转链表
    function reverseList(head, tail) {
        let prev = tail.next;
        let curr = head;
        while (prev !== tail) {
            const next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return [tail, head];
    }

    // 创建一个虚拟头节点
    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;

    while (head) {
        let tail = prev;
        // 找到第 k 个节点
        for (let i = 0; i < k; i++) {
            tail = tail.next;
            if (!tail) {
                return dummy.next;
            }
        }
        const next = tail.next;
        // 翻转 k 个节点
        [head, tail] = reverseList(head, tail);
        // 将翻转后的子链表连接到结果链表中
        prev.next = head;
        tail.next = next;
        // 更新 prev 和 head
        prev = tail;
        head = tail.next;
    }

    return dummy.next;
}

2. 递归法

递归法的思路是：

• 每次递归处理 K 个节点。
• 翻转这 K 个节点。
• 将翻转后的子链表连接到递归处理后的链表上。

function reverseKGroup(head, k) {
    // 辅助函数：翻转链表
    function reverseList(head, tail) {
        let prev = tail.next;
        let curr = head;
        while (prev !== tail) {
            const next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return [tail, head];
    }

    // 找到第 k 个节点
    let tail = head;
    for (let i = 0; i < k; i++) {
        if (!tail) {
            return head;
        }
        tail = tail.next;
    }

    // 翻转前 k 个节点
    const [newHead, newTail] = reverseList(head, tail);
    // 递归处理剩余的链表
    newTail.next = reverseKGroup(tail, k);

    return newHead;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。每个节点最多被遍历两次。
• 空间复杂度：O(1)（迭代法）或 O(n/k)（递归法，递归栈的深度）。

总结

K 个一组翻转链表是一个经典的链表操作问题，通过递归或迭代的方法可以有效地解决。迭代法通常更节省空间，而递归法则更直观易懂。在实际应用中，可以根据具体需求选择合适的方法。