【算法--链表】25.K个一组翻转链表--通俗讲解

一、题目是啥？一句话说清

给你一个链表，每k个节点一组进行反转，如果最后剩余的节点不足k个，则保持原状。需要实际交换节点，而不仅仅是改变值。

示例：

• 输入：head = [1,2,3,4,5], k = 2
• 输出：[2,1,4,3,5]（因为每2个一组反转，最后剩余5不足2个，保持原状）

二、解题核心

使用虚拟头节点简化操作，然后遍历链表，每次检查是否有k个节点，如果有则反转这k个节点，并正确连接反转后的组与前后部分。 这就像处理一列火车车厢，每k节车厢为一组进行调头，调头后还要重新连接好前后车厢。

三、关键在哪里？（3个核心点）

想理解并解决这道题，必须抓住以下三个关键点：

1. 虚拟头节点（Dummy Node）的使用

• 是什么：在原始链表前添加一个不存储实际数据的节点。
• 为什么重要：反转后头节点可能改变（例如原来头节点是1，反转后可能变成2），使用虚拟头节点可以避免单独处理头节点变化的特殊情况。

2. 分组检查与反转

• 是什么：每次反转前，先检查是否还有k个节点可供反转。如果不足k个，则保持剩余节点原状。
• 为什么重要：这确保了算法只反转完整的k个节点组，并正确处理剩余节点。

3. 连接反转后的组

• 是什么：反转一组节点后，需要将前一组节点的尾部与反转后的新头部连接，并将反转后的新尾部与下一组节点的头部连接。
• 为什么重要：如果连接不正确，链表会断开或形成环，导致错误。

四、看图理解流程（通俗理解版本）

让我们用链表 1 → 2 → 3 → 4 → 5 和 k=2 的例子来可视化过程：

1. 初始化：

   • 创建虚拟头节点 dummy，其 next 指向头节点 1。
   • 设置 pointer 指针指向 dummy，用于记录当前组的前一个节点。
   • 初始状态：dummy → 1 → 2 → 3 → 4 → 5

2. 第一组反转（反转1和2）：

   • 检查是否有2个节点：从pointer开始，有2个节点（1和2）。
   • 反转1和2：
     • 初始化：prev = null, curr = 1, next = null
     • 第一步：next = 2, curr.next = null, prev = 1, curr = 2
     • 第二步：next = 3, curr.next = 1, prev = 2, curr = 3
   • 反转后：2 → 1
   • 连接：pointer.next（dummy）指向2（新头），1（新尾）指向3（下一组的头）。
   • 更新 pointer 指向1（新尾）。
   • 当前链表：dummy → 2 → 1 → 3 → 4 → 5

3. 第二组反转（反转3和4）：

   • 检查是否有2个节点：从pointer（1）开始，有2个节点（3和4）。
   • 反转3和4：
     • 初始化：prev = null, curr = 3, next = null
     • 第一步：next = 4, curr.next = null, prev = 3, curr = 4
     • 第二步：next = 5, curr.next = 3, prev = 4, curr = 5
   • 反转后：4 → 3
   • 连接：pointer.next（1）指向4（新头），3（新尾）指向5（下一组的头）。
   • 更新 pointer 指向3（新尾）。
   • 当前链表：dummy → 2 → 1 → 4 → 3 → 5

4. 第三组检查：

   • 检查是否有2个节点：从pointer（3）开始，只有1个节点（5），不足2个，因此保持原状。
   • 结束循环。

5. 返回结果：返回 dummy.next，即新头节点2。

五、C++ 代码实现（附详细注释）

#include <iostream>
using namespace std;

// 链表节点定义
struct ListNode {
   
   
    <