链表困难1 种解法

#25K 个一组翻转链表

每 k 个节点组成一组原地翻转，末尾不足 k 个节点时保持原顺序。

#链表#分组#指针

解题主线

虚拟头节点统一处理第一组翻转，并让 groupPrevious 始终指向待翻转组的前驱。

先找到当前组第 k 个节点；若不存在就直接结束，保证不足 k 个的尾段不被修改。

把组后继作为反转初始 previous，可在反转完成时自然接回下一组，无需先断链。

解法 1：分组定位与迭代反转

逐组寻找第 k 个节点，以组后继为反转边界原地改向，再把新组头和新组尾接回主链。

时间复杂度

O(n)，每个节点被定位和翻转的总次数均为常数

空间复杂度

O(1)

25. K 个一组翻转链表 · 分组定位与迭代反转

java

final class Solution {
    static final class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (k <= 0) throw new IllegalArgumentException("k must be positive");
        if (head == null || k == 1) return head;

        ListNode dummy = new ListNode(0, head);
        ListNode groupPrevious = dummy;
        while (true) {
            ListNode kth = kthNode(groupPrevious, k);
            if (kth == null) break;
            ListNode groupNext = kth.next;

            ListNode previous = groupNext;
            ListNode current = groupPrevious.next;
            while (current != groupNext) {
                ListNode next = current.next;
                current.next = previous;
                previous = current;
                current = next;
            }

            ListNode oldGroupHead = groupPrevious.next;
            groupPrevious.next = kth;
            groupPrevious = oldGroupHead;
        }
        return dummy.next;
    }

    private ListNode kthNode(ListNode start, int k) {
        ListNode current = start;
        for (int i = 0; i < k && current != null; i++) {
            current = current.next;
        }
        return current;
    }
}

逐组寻找第 k 个节点，以组后继为反转边界原地改向，再把新组头和新组尾接回主链。

边界与易错点

翻转前必须保存 groupNext；第 k 个节点的 next 会在反转过程中被改写。
每组结束后，旧组头已经成为组尾，下一轮 groupPrevious 应移动到它。
旧实现使用递归反转单组，额外栈空间为 O(k)；整理后改为迭代反转，把额外空间降为 O(1)。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/zhard/Q025_reverseKGroup.java