链表

K 个一组翻转链表

困难#25Java时间 O(n)空间 O(1)

题目要做什么

每 k 个节点反转一组,最后不足 k 个节点时保持原顺序。节点值不变,原地改变连接。

题目示例输入head = [1,2,3,4,5], k = 2
题目示例输出[2,1,4,3,5]

01 为什么这样做

先检查是否有完整的 k 个节点,并保存下一组的头。把组内节点反转,最后连接前驱与新组头;原组头成为新尾和下一轮前驱。

始终成立的条件

groupPrev 之前的完整分组都已处理;groupNext 保存当前组之后的链表。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public ListNode reverseKGroup(ListNode head, int k) {3        ListNode dummy = new ListNode(0, head), groupPrev = dummy;4        while (true) {5            ListNode kth = groupPrev;6            for (int i = 0; i < k && kth != null; i++) kth = kth.next;7            if (kth == null) break;8            ListNode groupNext = kth.next;9            ListNode prev = groupNext, current = groupPrev.next;10            while (current != groupNext) {11                ListNode next = current.next;12                current.next = prev;13                prev = current; current = next;14            }15            ListNode oldHead = groupPrev.next;16            groupPrev.next = kth;17            groupPrev = oldHead;18        }19        return dummy.next;20    }21}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索