如何在Java中高效原地反转链表的k个一组节点？

我正在解决单链表的k个一组节点反转问题，要求实现原地算法（仅可使用少量额外变量）。尝试了多种方法，但难以得到符合要求的高效解决方案。具体需求如下：

• 以k个节点为一组进行反转；
• 若节点总数不是k的倍数，末尾剩余节点保持原有顺序；
• 必须采用原地实现。

示例：给定链表 1->2->3->4->5，k=3，输出应为 3->2->1->4->5。

以下是我的链表简化实现代码：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class ReverseKGroup {

public static ListNode reverseKGroup(ListNode head, int k) {
    // Implement the logic here
}

public static void main(String[] args) {
    ListNode head = new ListNode(1);
    head.next = new ListNode(2);
    head.next.next = new ListNode(3);
    head.next.next.next = new ListNode(4);
    head.next.next.next.next = new ListNode(5);

    int k = 3;
    ListNode newHead = reverseKGroup(head, k);

    // Print the reversed list
    while (newHead != null) {
        System.out.print(newHead.val + " -> ");
        newHead = newHead.next;
        }
    }
}

请问如何高效实现reverseKGroup方法以满足上述要求？希望能提供详细解释或代码示例！

要实现原地高效的K个一组反转，核心思路是分组处理+局部反转+组间衔接，整个过程仅使用常数级额外空间，时间复杂度为O(n)（n为链表节点总数）。

核心步骤拆解 #

• 哨兵节点（Dummy Node）：处理头节点反转后变化的问题，避免单独判断头节点，简化组间衔接逻辑。
• 分组检查：每次处理前，先确认剩余节点是否足够k个，不足则直接返回当前链表。
• 局部反转：对当前k个节点进行原地反转，记录反转前后的首尾节点，用于和前后组衔接。
• 组间衔接：将上一组的尾节点指向当前组反转后的头节点，同时更新当前组的尾节点为下一组的前置节点。

完整实现代码 #

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class ReverseKGroup {

    public static ListNode reverseKGroup(ListNode head, int k) {
        // 哨兵节点，简化头节点处理
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // prevTail 记录上一组反转后的尾节点，初始为哨兵节点
        ListNode prevTail = dummy;
        
        while (true) {
            // 检查剩余节点是否够k个
            ListNode current = prevTail.next;
            int count = 0;
            while (current != null && count < k) {
                current = current.next;
                count++;
            }
            // 不足k个，直接结束循环
            if (count != k) break;
            
            // 反转当前k个节点，返回反转后的头节点
            ListNode reversedHead = reverse(prevTail.next, k);
            // 记录当前组反转前的头节点（即反转后的尾节点）
            ListNode currentTail = prevTail.next;
            // 上一组尾节点指向当前组反转后的头节点
            prevTail.next = reversedHead;
            // 更新prevTail为当前组的尾节点，准备下一组处理
            prevTail = currentTail;
        }
        
        return dummy.next;
    }
    
    // 辅助方法：反转从head开始的k个节点，返回反转后的头节点
    private static ListNode reverse(ListNode head, int k) {
        ListNode prev = null;
        ListNode curr = head;
        while (k > 0) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
            k--;
        }
        // 反转后，原head（当前组尾节点）指向未反转的下一组首节点
        head.next = curr;
        return prev;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        int k = 3;
        ListNode newHead = reverseKGroup(head, k);

        // 打印结果链表
        while (newHead != null) {
            System.out.print(newHead.val);
            if (newHead.next != null) {
                System.out.print(" -> ");
            }
            newHead = newHead.next;
        }
    }
}

关键细节解释 #

1. 哨兵节点的作用：第一组反转后，原头节点会变成组内尾节点，新的链表头是组内最后一个节点。用哨兵节点指向原头节点，后续直接返回dummy.next即可得到新链表头，无需单独处理头节点的特殊情况。
2. 分组检查逻辑：每次循环前先遍历k个节点，确认剩余节点数量足够。如果不足，直接跳出循环，保证末尾剩余节点不被反转。
3. 局部反转的衔接：reverse方法中，反转完成后，原头节点（当前组尾节点）需要指向未反转的下一组首节点，避免链表断裂。
4. 组间衔接：prevTail始终记录上一组的尾节点，每次反转完当前组后，将prevTail.next指向当前组反转后的头节点，再更新prevTail为当前组的尾节点，为下一次循环做准备。

复杂度分析 #

• 时间复杂度：O(n)，每个节点最多被访问两次（一次分组检查，一次反转）。
• 空间复杂度：O(1)，仅使用常数个额外变量，符合原地算法要求。

内容的提问来源于stack exchange，提问作者Ashini Ayodhya