给你链表的头节点 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) 额外内存空间的算法解决此问题吗？
步骤 1：问题分析
问题性质：
- 给定一个单链表
head，需要每k个节点为一组进行翻转，返回翻转后的链表。 - 如果链表长度不是
k的整数倍，则最后不足k个节点的部分不翻转，保持原顺序。
输入输出条件：
- 输入：链表头节点
head和正整数k。 - 输出：修改后的链表头节点。
限制：
- 链表节点数
n在[1, 5000]范围内。 1 <= k <= n <= 5000。- 仅能进行节点交换，不能更改节点的值。
边界条件：
k = 1：不需要任何反转，直接返回链表。n < k：链表长度小于k，则不进行任何操作，直接返回链表。k = n：链表整体需要翻转一次。
步骤 2：解题思路
我们可以分组进行局部翻转，用双指针法进行链表分段，并通过指针操作进行局部反转，保持空间复杂度为 O(1)。
算法设计思路：
-
遍历链表，按 k 个分段：
- 首先遍历链表来获取节点总数
n，计算有多少完整的k段可以进行翻转。
- 首先遍历链表来获取节点总数
-
逐组反转：
- 使用一个虚拟节点
dummy来简化头节点翻转的情况，dummy->next指向head。 - 设置一个指针
prev来跟踪每一组的前驱节点，最初指向dummy。 - 对每个完整的
k段进行翻转，翻转后更新prev，指向这一段的结尾节点，准备开始下一段翻转。
- 使用一个虚拟节点
-
执行翻转：
- 对每个
k长度的组，使用双指针cur和next实现局部反转。 - 在每一轮的反转中，将当前节点的
next指向前驱，逐个调整，形成反转后的组链表。
- 对每个
-
剩余节点保持不变：
- 如果剩下的节点不足
k个，则直接返回，不对剩余部分操作。
- 如果剩下的节点不足
复杂度分析：
- 时间复杂度：O(n)，因为我们最多遍历链表两次（一次统计长度，一次进行翻转）。
- 空间复杂度：O(1)，因为只用到常量级的辅助指针。
步骤 3：C++代码实现
代码详解
- 初始化
dummy：创建一个虚拟节点dummy，dummy->next指向head，用来简化链表头部处理的边界情况。 - 计算链表长度：遍历链表，记录链表长度
length，判断需要翻转的次数。 - 按
k个节点为一组翻转：- 使用
cur和next指针来逐个反转组内的节点。 - 每次反转都调整当前节点的
next指向，形成局部的链表反转。
- 使用
- 更新
prev：每次完成k个节点的翻转后，将prev更新到当前翻转段的结尾节点，为下一组翻转做准备。 - 返回结果：最终返回
dummy->next，即翻转后的链表头。
步骤 4：启发与算法优化
-
局部翻转的技巧：使用双指针实现链表局部翻转，节省空间的同时提高了效率。这种技巧可用于链表的其他翻转和旋转操作。
-
优化时间复杂度：通过一次遍历得到链表长度，然后用双指针实现局部反转，避免了多次遍历，实现了
O(n)的时间复杂度。 -
链表题的边界处理：通过使用
dummy节点，可以简化对头节点的特殊处理。dummy节点是链表题中非常实用的技巧，使链表操作统一，无需额外判断头节点的边界情况。
步骤 5：实际应用
应用场景： 在实际中，链表分组翻转的算法在数据处理和批量更新方面非常有用。例如：
-
内存块反转：在存储器管理中，可以使用链表结构管理内存块，并对内存块按组进行翻转，以均衡访问时间或分配负载。
-
实时数据流处理：对于实时数据流管理，如果需要分批处理一定量的数据，类似的链表分组翻转算法可以确保数据流按需排序和管理。
示例应用： 在实时传感器数据的分析系统中，假设每次采集的数据以链表形式存储，传感器数据的批量反转可以确保数据以指定的分组进行处理。例如，数据组按 k=5 的分组翻转后，每 5 个数据作为一个批次处理，方便数据整合和批量传输，提高数据分析系统的响应速度。
通过上述方法，可以实现实时数据的批量反转，使得系统按需求对数据流分组处理，提升了数据传输和分析的效率。
