面试经典150题——K 个一组翻转链表

1. 题目描述

2. 题目分析与解析

在这里推荐大家看一下这个解题思路：

https://www.bilibili.com/video/BV11w411V7Ar/?spm_id_from=333.337.search-card.all.click&vd_source=7ea7c036902f5cb73c7f4781d1b0eaff

整体的算法思路如下：

1. 初始化：

   • 创建一个虚拟头节点 dummy，并将其 next 指针指向原链表的头节点 head。这是为了在翻转包含头节点的子链表时能够方便地处理。
   • 定义 cur 指针并指向 dummy，用于标记当前处理的子链表的前一个节点。

2. 翻转过程：

   • 开启一个循环，直到 cur 为空。
   • 在每次循环中，尝试翻转从 cur.next 开始的 k 个节点，并将翻转后的子链表头返回给 cur.next，以此来实现链表的局部翻转。

3. 移动 cur 指针：

   • 翻转完成后，将 cur 指针移动 k 个节点，准备下一轮的翻转操作。这里使用了一个 for 循环来确保 cur 正确移动。

4. 翻转函数 reverse：

   • 先通过遍历计算出从 head 开始的子链表的实际长度 n。
   • 如果长度小于 k，说明剩余节点不足 k 个，不需要翻转，直接返回原 head。
   • 如果长度足够，使用三个指针 pre、slow 和 fast 实现局部翻转。
   • pre 初始化为 null，作为已翻转部分的尾节点；slow 初始化为 head，作为当前要翻转的节点；fast 初始化为 head.next，作为下一个要翻转的节点。
   • 通过迭代，将 slow.next 指向 pre，然后依次更新 pre、slow 和 fast，完成 k 个节点的翻转。

5. 翻转后的连接：

   • 翻转后，原链表的 head 节点变成了新的尾节点，需要将其 next 指向 fast，以连接翻转段之后的链表部分。

6. 结果返回：

   • 翻转操作完成后，通过 dummy.next 返回新链表的头节点。

3. 代码实现

4. 相关复杂度分析

时间复杂度：

1. 对于整个链表的遍历，即使有两层循环结构（一个是while循环，另一个是reverse函数中的while循环），每个节点仍然只被访问了常数次（最多两次，一次是在判断是否有足够的节点进行下一次翻转，一次是在实际翻转中）。因此，遍历链表的时间复杂度是 O(n)，其中 n 是链表中的节点数量。

2. reverse函数会被调用 n/k 次（因为每次翻转 k 个节点），每次翻转操作需要 O(k) 的时间。但由于这些操作是并行的，总体上仍然是 O(n)。

因此，整个算法的时间复杂度是 O(n)。

空间复杂度：

1. 虚拟头节点 dummy 和指针 cur、pre、slow、fast 都只需要常数空间。

2. 算法没有使用额外的数据结构来存储节点或其他信息，所有操作都是在原链表上直接进行的。

3. reverse函数是递归调用的，但由于它在每次翻转后都会断开递归调用，因此不会在栈上累积大量的调用帧。

综上所述，算法的空间复杂度是 O(1)，也就是常数空间复杂度，满足题目要求使用常数级额外空间的约束。