链表困难1 种解法
#25K 个一组翻转链表
每 k 个节点组成一组原地翻转，末尾不足 k 个节点时保持原顺序。
#链表#分组#指针
原题
给你链表的头节点 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]提示：
- 链表中的节点数目为
n 1 <= k <= n <= 50000 <= Node.val <= 1000
进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
解题主线
- 虚拟头节点统一处理第一组翻转，并让 groupPrevious 始终指向待翻转组的前驱。
- 先找到当前组第 k 个节点；若不存在就直接结束，保证不足 k 个的尾段不被修改。
- 把组后继作为反转初始 previous，可在反转完成时自然接回下一组，无需先断链。
解法 1：分组定位与迭代反转
逐组寻找第 k 个节点，以组后继为反转边界原地改向，再把新组头和新组尾接回主链。
-
时间复杂度： O(n)，每个节点被定位和翻转的总次数均为常数
-
空间复杂度： O(1)
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) {
// 先确认本组恰有 k 个节点；不足 k 个时保持尾段原样。
ListNode kth = kthNode(groupPrevious, k);
if (kth == null) break;
ListNode groupNext = kth.next;
// 以组后继作为初始 previous，反转后新组尾会自然接回后续链表。
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;
// 从组前驱向后走 k 步，返回当前组末节点或 null。
for (int i = 0; i < k && current != null; i++) {
current = current.next;
}
return current;
}
}边界与易错点
- 翻转前必须保存 groupNext；第 k 个节点的 next 会在反转过程中被改写。
- 每组结束后，旧组头已经成为组尾，下一轮 groupPrevious 应移动到它。
- 旧实现使用递归反转单组，额外栈空间为 O(k)；整理后改为迭代反转，把额外空间降为 O(1)。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/zhard/Q025_reverseKGroup.java