Day 12。
今天两道题分别是 Swap Nodes in Pairs 和 Reverse Nodes in k-Group。
这两题放在一起看特别有意思，因为它们本质上都属于：

链表分组操作

一道是两两交换，一道是每 k 个一组翻转。
今天的关键词：链表分组、指针重连、虚拟头结点、局部翻转、栈辅助。

🧠 LeetCode 24 – Swap Nodes in Pairs

💡 思路总结

这题要求把链表中的节点两两交换。

比如：

1 -> 2 -> 3 -> 4

交换后变成：

2 -> 1 -> 4 -> 3

这题的关键不是交换值，而是：

直接交换节点本身

你的思路是标准的链表指针重连做法：

  1. 用 prev 指向当前这一组前面的节点
  2. 用 curr 指向当前组的第一个节点
  3. 用 node 指向当前组的第二个节点
  4. 重新连边，完成交换
  5. 再移动到下一组继续处理

💻 代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr)return nullptr;
        if(head ->next == nullptr)return head;
        ListNode dummy(0);
        ListNode* prev = &dummy;
        ListNode* nextPair;
        ListNode* curr = head;
        while(curr != nullptr && curr->next != nullptr){
            ListNode* node = curr->next;
            nextPair = node->next;
            prev->next = node;
            curr->next = node->next;
            node->next = curr;
            //交换完毕；
            prev = curr;
            curr = nextPair;
        }
        return dummy.next;
    }
};

📌 知识点总结

1️⃣ 这是典型的链表局部交换

数组里交换两个元素很简单，直接 swap 就行。
但链表里交换节点，真正要做的是：

  • 改前驱指针
  • 改当前节点指针
  • 改后继指针

所以链表题的本质经常不是“值怎么变”，而是：

指针怎么重新连接

2️⃣ 虚拟头结点继续立功

你这里用了：

ListNode dummy(0);
ListNode* prev = &dummy;

这个写法很对。
因为链表头节点也可能参与交换，加入虚拟头结点后，所有交换逻辑都统一了，不需要单独特判头节点。

不过这里有一个小细节：

你少写了一句：

dummy.next = head;

没有这句的话，prev->next = node 虽然在循环里能接上第一组，但如果链表一开始就不进入循环，或者从整体逻辑上看，dummy 和原链表的连接不够完整。
更规范、更稳妥的写法应该把 dummy.next 先指向 head。

✅ 更稳一点的版本

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;
        ListNode* curr = head;

        while (curr != nullptr && curr->next != nullptr) {
            ListNode* node = curr->next;
            ListNode* nextPair = node->next;

            prev->next = node;
            node->next = curr;
            curr->next = nextPair;

            prev = curr;
            curr = nextPair;
        }

        return dummy.next;
    }
};

3️⃣ 两两交换其实是“2 个一组翻转”

这题也可以从另一个角度理解：

每次把长度为 2 的链表片段翻转

这样你会发现，它和后面的 Reverse Nodes in k-Group 其实是一脉相承的。

🔥 LeetCode 25 – Reverse Nodes in k-Group

💡 思路总结

这题要求把链表每 k 个节点分成一组进行翻转。
如果最后剩余节点不足 k 个，就保持原样。

比如：

1 -> 2 -> 3 -> 4 -> 5, k = 2

结果是：

2 -> 1 -> 4 -> 3 -> 5

如果：

1 -> 2 -> 3 -> 4 -> 5, k = 3

结果是：

3 -> 2 -> 1 -> 4 -> 5

你的做法挺清晰，是：

  1. 先检查当前这一段是否够 k 个节点
  2. 如果不够，直接接上剩余部分
  3. 如果够，就调用 reverseK 翻转这一组
  4. 再更新尾指针和当前指针，继续处理下一组

这已经是一个很完整的分组处理框架了。

💻 代码实现

#include <stack>
using namespace std;

class Solution {
public:
    ListNode* reverseK(ListNode* head, int k) {
        ListNode* curr = head;
        int i = 0;
        stack<ListNode*> st;

        while (i != k) {
            if (curr == nullptr) return head;  // 不够 k 个，返回原头
            st.push(curr);
            curr = curr->next;
            i++;
        }

        ListNode* nextKGroup = curr;  // 第 k+1 个节点

        ListNode dummy(0);
        ListNode* tail = &dummy;

        while (!st.empty()) {
            ListNode* node = st.top();
            st.pop();
            tail->next = node;
            tail = tail->next;
        }

        tail->next = nextKGroup;
        return dummy.next;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == nullptr || k == 1) return head;

        ListNode dummy(0);
        ListNode* tail = &dummy;
        ListNode* curr = head;

        while (curr != nullptr) {
            // 先检查从 curr 开始是否有 k 个节点
            ListNode* check = curr;
            int cnt = 0;
            while (cnt < k && check != nullptr) {
                check = check->next;
                cnt++;
            }

            // 不够 k 个，直接接上剩余部分，结束
            if (cnt < k) {
                tail->next = curr;
                break;
            }

            // 记录这一组翻转前的头，它翻转后会变成尾
            ListNode* oldHead = curr;

            // 翻转这一组
            ListNode* newHead = reverseK(curr, k);
            tail->next = newHead;

            // 更新 tail 和 curr
            tail = oldHead;
            curr = oldHead->next;
        }

        return dummy.next;
    }
};

📌 知识点总结

1️⃣ 这题本质是“链表按组处理”

和前一题的两两交换相比，这题只是把“每组 2 个”扩展成了“每组 k 个”。

所以本质模型是一样的：

  • 先确定这一组范围
  • 对这一组做局部操作
  • 再把处理后的结果接回整体链表

这类题的关键不是翻转本身，而是：

分组、翻转、接回去

2️⃣ 用栈实现局部翻转

你这里的 reverseK 用了栈：

  • 顺序把 k 个节点压进去
  • 再依次弹出
  • 就得到了逆序效果

这个思路很好理解，因为栈天然就是后进先出。

也就是说，你这里实际上是把：

链表翻转问题
转化成了
栈逆序输出问题

对当前阶段来说，这个写法很直观。

3️⃣ 为什么要先检查够不够 k 个

这题有个重要规则：

不足 k 个节点时，不翻转

所以你先写了这一段检查：

ListNode* check = curr;
int cnt = 0;
while (cnt < k && check != nullptr) {
    check = check->next;
    cnt++;
}

这是非常关键的。
没有这一步，就可能把不完整的一组也误翻转掉。

4️⃣ oldHead 的作用很巧

这一句很重要：

ListNode* oldHead = curr;

因为当前组翻转之后：

  • 原来的头节点
  • 会变成这一组的尾节点

所以后面你写：

tail = oldHead;
curr = oldHead->next;

逻辑上就能衔接下一组。

这说明你已经开始能看懂链表翻转前后“头尾身份变化”的问题了，这很不错。

5️⃣ 这题还能继续优化

你现在这版思路清楚，能很好表达“分组 + 翻转”的框架。
不过从空间复杂度上看，栈会多用 O(k) 的额外空间。

这题还有一种更经典的写法：

直接在链表上原地翻转

那样可以做到 O(1) 额外空间。
当然那种写法更绕，指针操作也更复杂。你现在先把这版真正理解透，比直接上最难写法更有价值。

🧩 今日总结

题目核心思想
LeetCode 24虚拟头结点 + 两两交换 + 指针重连
LeetCode 25分组检查 + 栈辅助翻转 + 链表拼接

今天两道题其实联系特别紧：

  • 24 可以看成 k = 2 的特殊情况
  • 25 是更一般化的按组翻转

这说明链表题里很多题并不是完全独立的，而是一条主线不断展开。

🧠 今日收获

今天最值得记住的两个模型：

1. 链表局部操作题

看到这种题，优先想：

  • 这一小段的头是谁
  • 这一小段的尾是谁
  • 前驱怎么连
  • 后继怎么接

本质就是：局部改完，再拼回整体。

2. 分组处理思想

很多链表题不是一个节点一个节点做，而是：

  • 每两个一组
  • 每 k 个一组
  • 每一段一组

所以一定要开始习惯把链表题看成“分块处理”。

💬 写给自己的话

Day 12 了。

你已经开始刷到一些真正“有链表味儿”的题了。
这种题通常不是思路难，而是：

  • 指针容易乱
  • 头尾容易绕
  • 局部和整体容易接错

但你现在已经在慢慢适应这种感觉了。

这很重要。
因为链表题真正的进步，不是背下来某一题代码，
而是你开始能意识到：

我现在改的这条指针，会影响哪一段链表。

这就是成长。

继续坚持，继续总结，继续磨指针。
等你把这些分组翻转、局部交换题都练熟，链表这一块你就会越来越稳。

阿玉，Day 12，继续冲。

—— 刷题第 12 天