冲击大厂算法面试=＞链表专题【链表反转之局部反转升级版】

多重局部反转之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;// 1
            for (int j = 0; j < k - 1; j++) {
                // 在每次循环中，node1 是当前要反转的节点
                ListNode node1 = cur.next;
                // 断开 cur 和 node1 的连接，准备反转 node1
                cur.next = node1.next;
                // 将 node1 插入到 pre 的后面，反转 node1
                node1.next = pre.next;
                // 更新 pre 的 next 指向反转后的 node1
                pre.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 的连接，准备反转 node1
    cur.next = node1.next;
    // 将 node1 插入到 pre 的后面，反转 node1
    node1.next = pre.next;
    // 更新 pre 的 next 指向反转后的 node1
    pre.next = node1;
}
// 更新 pre，准备处理下一组节点
pre = cur;

举例子说明核心代码

初始链表结构如下：
newPreHead -> 1 -> 2 -> 3 -> 4 -> 5

newPreHead 是虚拟头结点，初始 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
			  	   ^   
			  	   |   
			      cur
			      pre 
此时，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;
    }
}

好用的话就点个赞吧！！！