目录标题
- 多重局部反转之K 个一组翻转链表
- 上代码
- 题解呀
- 实在不会的时候记住
多重局部反转之K 个一组翻转链表
上代码
整个函数通过不断地检查剩余节点数量和进行局部反转，实现了链表的分组反转，最后返回反转后的链表。这种方法有效地利用了额外的 pre 和 cur 指针来跟踪反转过程，避免了复杂的数据结构和额外的空间消耗。
class Solution {public ListNode reverseKGroup(ListNode head, int k) {//头节点法ListNode newPreHead = new ListNode(-1);newPreHead.next = head;ListNode pre = newPreHead;// 原地反转while (true) {// 检查剩余节点是否有k个，不足则返回ListNode innerCur = pre;int i = 0;while (i < k) {innerCur = innerCur.next;i++;if (innerCur == null) {return newPreHead.next;}}// 翻转k个节点,操作k-1次就行// 1 2 3 -> 2 1 3// 目标：反转从 pre.next 开始的 k 个节点ListNode cur = pre.next;// 1for (int j = 0; j < k - 1; j++) {// 在每次循环中，node1 是当前要反转的节点ListNode node1 = cur.next;// 断开 cur 和 node1 的连接，准备反转 node1cur.next = node1.next;// 将 node1 插入到 pre 的后面，反转 node1node1.next = pre.next;// 更新 pre 的 next 指向反转后的 node1pre.next = node1;}// 更新 pre，准备处理下一组节点pre = cur;}}
}
题解呀
本题的难点在于连续的局部反转
核心代码：
// 翻转k个节点,操作k-1次就行
// 1 2 3 -> 2 1 3
// 目标：反转从 pre.next 开始的 k 个节点
ListNode cur = pre.next;// 1
for (int j = 0; j < k - 1; j++) {// 在每次循环中，node1 是当前要反转的节点ListNode node1 = cur.next;// 断开 cur 和 node1 的连接，准备反转 node1cur.next = node1.next;// 将 node1 插入到 pre 的后面，反转 node1node1.next = pre.next;// 更新 pre 的 next 指向反转后的 node1pre.next = node1;
}
// 更新 pre，准备处理下一组节点
pre = cur;
举例子说明核心代码
初始链表结构如下：
newPreHead -> 1 -> 2 -> 3 -> 4 -> 5newPreHead 是虚拟头结点，初始 pre 指向 newPreHead。
cur 指向 1，即当前组的第一个节点。
node1 将在反转过程中表示下一个要反转的节点。
-----------------------------------
第一次反转（k=2）
步骤 1: 初始化 cur 和 node1
newPreHead -> 1 -> 2 -> 3 -> 4 -> 5^ ^ ^| | |pre cur node1
-----------------------------------步骤 2: 断开 cur 和 node1 的连接，准备反转 node1
【cur.next = node1.next;】2
newPreHead -> 1 -> - -> 3 -> 4 -> 5^ ^ ^| | |pre cur node1-----------------------------------
步骤 3: 将 node1 插入到 pre 后面，反转 node1
【node1.next = pre.next;】<-<-<-| |∨ 2
newPreHead -> 1 -> - ->3 -> 4 -> 5^ ^ ^| | |pre cur node1步骤 4:再次执行【pre.next = node1;】| -> -> -> -> -> -> >| || <-<-<- | | | | | | ∨ 2 < -
newPreHead 1 -> - ->3 -> 4 -> 5^ ^ ^| | |pre cur node1-----------------------------------
步骤 5: 更新 pre，准备处理下一组节点
【 pre = cur;】
newPreHead -> 2 -> 1 -> 3 -> 4 -> 5^ | curpre
此时，pre.next 指向了 2，node1.next 指向了 1，完成了第一次反转。
第二轮初始化就会变成，node1=4成为要反转的点
newPreHead -> 2 -> 1 -> 3 -> 4 -> 5^ ^ ^| | | pre cur node1
-----------------------------------
直到循环结束
实在不会的时候记住
通过数据结构来简化问题
class Solution {public ListNode reverseKGroup(ListNode head, int k) {Deque<ListNode> stack = new ArrayDeque<ListNode>();ListNode dummy = new ListNode(0);ListNode p = dummy;while (true) {int count = 0;ListNode tmp = head;//我们把 k 个数压入栈中，然后弹出来的顺序就是翻转的while (tmp != null && count < k) {stack.add(tmp);tmp = tmp.next;count++;}//不相等 说明到最后了 退出if (count != k) {//不翻转p.next = head;break;}//栈不为空 翻转while (!stack.isEmpty()){p.next = stack.pollLast();p = p.next;}head = tmp;}return dummy.next;}
}
好用的话就点个赞吧！！！
