链表（典型算法思想）—— OJ例题算法解析思路

目录

一、2. 两数相加 - 力扣（LeetCode）

算法代码： 

1. 初始化

2. 遍历链表并相加

3. 返回结果

举例说明

二、24. 两两交换链表中的节点 - 力扣（LeetCode）

算法代码： 

代码思路

举例说明

初始状态

第一次交换

第二次交换

最终结果

三、143. 重排链表 - 力扣（LeetCode） 

算法代码： 

代码思路

举例说明

初始状态

1. 找到中间节点

2. 逆序后半部分链表

3. 合并两个链表

最终结果

代码总结

执行步骤总结

四、23. 合并 K 个升序链表 - 力扣（LeetCode）

解法一：算法代码（利用堆） 

代码思路

举例说明

初始状态

执行过程

最终结果

代码总结

执行步骤总结

解法二：算法代码（递归/分治）

代码分析

1. 类的结构

2. 主函数 - mergeKLists

3. 分治法 - merge

4. 平分数组与递归

5. 合并两个有序链表 - mergeTowList

6. 合并过程

7. 合并逻辑

8. 处理剩余节点

举例说明

合并过程

五、25. K 个一组翻转链表 - 力扣（LeetCode） 

算法代码： 

代码分析

1. 链表节点结构定义

2. 主函数 - reverseKGroup

3. 逆序过程

4. 处理不需要翻转的部分

举例说明

处理过程

总结

---

一、2. 两数相加 - 力扣（LeetCode）

算法代码： 

/*** 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* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *cur1 = l1, *cur2 = l2;ListNode* newhead = new ListNode(0); // 创建⼀个虚拟头结点，记录最终结果ListNode* prev = newhead;            // 尾指针int t = 0;                           // 记录进位while (cur1 || cur2 || t) {// 先加上第⼀个链表if (cur1) {t += cur1->val;cur1 = cur1->next;}// 加上第⼆个链表if (cur2) {t += cur2->val;cur2 = cur2->next;}prev->next = new ListNode(t % 10);prev = prev->next;t /= 10;}prev = newhead->next;delete newhead;return prev;}
};

1. 初始化

• 创建两个指针 cur1 和 cur2，分别指向两个链表的头节点 l1 和 l2。

• 创建一个虚拟头节点 newhead，用于记录最终的结果链表。这个虚拟头节点的作用是简化链表操作，避免处理头节点的特殊情况。

• 创建一个尾指针 prev，指向当前结果链表的最后一个节点。

• 初始化一个变量 t，用于记录进位。

2. 遍历链表并相加

• 使用 while 循环遍历两个链表，直到两个链表都遍历完且没有进位为止。

• 在循环中：

  • 如果 cur1 不为空，将 cur1 的值加到 t 上，并将 cur1 指向下一个节点。

  • 如果 cur2 不为空，将 cur2 的值加到 t 上，并将 cur2 指向下一个节点。

  • 将 t % 10 的值作为新节点的值，并将其添加到结果链表的末尾。

  • 更新 prev 指针，使其指向新添加的节点。

  • 更新 t 为 t / 10，即计算进位。

3. 返回结果

• 循环结束后，结果链表的头节点是 newhead->next。

• 删除虚拟头节点 newhead，避免内存泄漏。

• 返回结果链表的头节点。

举例说明

假设有两个链表 l1 和 l2，分别表示数字 342 和 465，即：

• l1: 2 -> 4 -> 3

• l2: 5 -> 6 -> 4

按照代码的逻辑，相加过程如下：

1. 初始化:

   • cur1 指向 2，cur2 指向 5。

   • newhead 是一个虚拟头节点，prev 指向 newhead。

   • t = 0。

2. 第一次循环:

   • t = 0 + 2 + 5 = 7。

   • 创建新节点 7，prev->next 指向 7，prev 指向 7。

   • t = 7 / 10 = 0。

   • cur1 指向 4，cur2 指向 6。

3. 第二次循环:

   • t = 0 + 4 + 6 = 10。

   • 创建新节点 0，prev->next 指向 0，prev 指向 0。

   • t = 10 / 10 = 1。

   • cur1 指向 3，cur2 指向 4。

4. 第三次循环:

   • t = 1 + 3 + 4 = 8。

   • 创建新节点 8，prev->next 指向 8，prev 指向 8。

   • t = 8 / 10 = 0。

   • cur1 和 cur2 都为 nullptr，循环结束。

5. 返回结果:

   • 结果链表为 7 -> 0 -> 8，表示数字 807，即 342 + 465 = 807。

二、24. 两两交换链表中的节点 - 力扣（LeetCode）

算法代码： 

/*** 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 || head->next == nullptr)return head;ListNode* newHead = new ListNode(0);newHead->next = head;ListNode *prev = newHead, *cur = prev->next, *next = cur->next,*nnext = next->next;while (cur && next) {// 交换结点prev->next = next;next->next = cur;cur->next = nnext;// 修改指针prev = cur; // 注意顺序cur = nnext;if (cur)next = cur->next;if (next)nnext = next->next;}cur = newHead->next;delete newHead;return cur;}
};

代码思路

1. 检查边界条件：

   • 如果链表为空（head == nullptr）或只有一个节点（head->next == nullptr），直接返回 head，因为不需要交换。

2. 创建虚拟头节点：

   • 创建一个虚拟头节点 newHead，并将其 next 指向链表的头节点 head。虚拟头节点的作用是简化头节点的交换操作，避免特殊处理。

3. 初始化指针：

   • prev：指向当前节点对的前一个节点（初始为 newHead）。

   • cur：指向当前节点对中的第一个节点（初始为 head）。

   • next：指向当前节点对中的第二个节点（初始为 cur->next）。

   • nnext：指向 next 的下一个节点（初始为 next->next）。

4. 遍历链表并交换节点：

   • 使用 while 循环遍历链表，直到 cur 或 next 为空。

   • 在循环中：

     1. 交换节点：

        • 将 prev->next 指向 next。

        • 将 next->next 指向 cur。

        • 将 cur->next 指向 nnext。

     2. 更新指针：

        • 将 prev 指向 cur（当前节点对中的第一个节点）。

        • 将 cur 指向 nnext。

        • 如果 cur 不为空，将 next 指向 cur->next。

        • 如果 next 不为空，将 nnext 指向 next->next。

5. 返回结果：

   • 将 cur 指向 newHead->next（交换后的链表头节点）。

   • 删除虚拟头节点 newHead，释放内存。

   • 返回 cur（交换后的链表）。

---

举例说明

假设链表为 1 -> 2 -> 3 -> 4，交换过程如下：

初始状态

• newHead -> 1 -> 2 -> 3 -> 4

• prev = newHead

• cur = 1

• next = 2

• nnext = 3

第一次交换

1. 交换节点：

   • prev->next 指向 2。

   • next->next 指向 1。

   • cur->next 指向 3。

2. 更新指针：

   • prev = 1。

   • cur = 3。

   • next = 4。

   • nnext = nullptr（因为 next->next 为空）。

第二次交换

1. 交换节点：

   • prev->next 指向 4。

   • next->next 指向 3。

   • cur->next 指向 nullptr。

2. 更新指针：

   • prev = 3。

   • cur = nullptr（因为 nnext 为空）。

   • 循环结束。

最终结果

• 交换后的链表为 2 -> 1 -> 4 -> 3。

• 删除虚拟头节点 newHead。

• 返回 2 作为链表的头节点。

三、143. 重排链表 - 力扣（LeetCode） 

算法代码： 

/*** 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:void reorderList(ListNode* head) {// 处理边界情况if (head == nullptr || head->next == nullptr ||head->next->next == nullptr)return;// 1. 找到链表的中间节点 - 快慢双指针（⼀定要画图考虑 slow// 的落点在哪⾥）ListNode *slow = head, *fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}// 2. 把 slow 后⾯的部分给逆序 - 头插法ListNode* head2 = new ListNode(0);ListNode* cur = slow->next;slow->next = nullptr; // 注意把两个链表给断开while (cur) {ListNode* next = cur->next;cur->next = head2->next;head2->next = cur;cur = next;}// 3. 合并两个链表 - 双指针ListNode* ret = new ListNode(0);ListNode* prev = ret;ListNode *cur1 = head, *cur2 = head2->next;while (cur1) {// 先放第⼀个链表prev->next = cur1;cur1 = cur1->next;prev = prev->next;// 再放第⼆个链表if (cur2) {prev->next = cur2;prev = prev->next;cur2 = cur2->next;}}delete head2;delete ret;}
};

代码思路

1. 处理边界情况：

   • 如果链表为空（head == nullptr）、只有一个节点（head->next == nullptr）或只有两个节点（head->next->next == nullptr），直接返回，因为不需要重排。

2. 找到链表的中间节点：

   • 使用 快慢双指针：

     • slow 指针每次移动一步。

     • fast 指针每次移动两步。

   • 当 fast 到达链表末尾时，slow 指向链表的中间节点。

   • 将链表从中间节点断开，分为前半部分和后半部分。

3. 逆序后半部分链表：

   • 使用 头插法 将后半部分链表逆序：

     • 创建一个虚拟头节点 head2。

     • 遍历后半部分链表，将每个节点插入到 head2 的后面。

   • 最终，head2->next 指向逆序后的后半部分链表。

4. 合并两个链表：

   • 使用 双指针 将前半部分链表和逆序后的后半部分链表合并：

     • cur1 指向前半部分链表的头节点。

     • cur2 指向逆序后的后半部分链表的头节点。

     • 依次交替连接两个链表的节点。

   • 最终，链表被重排为所需顺序。

5. 释放临时节点：

   • 删除虚拟头节点 head2 和 ret，释放内存。

---

举例说明

假设链表为 1 -> 2 -> 3 -> 4 -> 5，重排过程如下：

初始状态

• 链表：1 -> 2 -> 3 -> 4 -> 5。

1. 找到中间节点

• slow 指向 3，fast 指向 5。

• 将链表从 3 断开：

  • 前半部分：1 -> 2 -> 3。

  • 后半部分：4 -> 5。

2. 逆序后半部分链表

• 逆序后的后半部分链表：5 -> 4。

3. 合并两个链表

• 交替连接节点：

  • 1 -> 5 -> 2 -> 4 -> 3。

最终结果

• 重排后的链表为 1 -> 5 -> 2 -> 4 -> 3。

---

代码总结

1. 快慢双指针：

   • 用于找到链表的中间节点，确保链表被正确分为两部分。

2. 头插法逆序链表：

   • 将后半部分链表逆序，便于后续合并。

3. 双指针合并链表：

   • 交替连接两个链表的节点，完成重排。

4. 边界条件处理：

   • 确保代码在链表节点数较少时也能正常运行。

---

执行步骤总结

1. 找到中间节点并断开链表。

2. 逆序后半部分链表。

3. 合并前半部分和逆序后的后半部分链表。

4. 释放临时节点，返回重排后的链表。

四、23. 合并 K 个升序链表 - 力扣（LeetCode）

解法一：算法代码（利用堆） 

/*** 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 {struct cmp {bool operator()(const ListNode* l1, const ListNode* l2) {return l1->val > l2->val;}};public:ListNode* mergeKLists(vector<ListNode*>& lists) {// 创建⼀个⼩根堆priority_queue<ListNode*, vector<ListNode*>, cmp> heap;// 让所有的头结点进⼊⼩根堆for (auto l : lists)if (l)heap.push(l);// 合并 k 个有序链表ListNode* ret = new ListNode(0);ListNode* prev = ret;while (!heap.empty()) {ListNode* t = heap.top();heap.pop();prev->next = t;prev = t;if (t->next)heap.push(t->next);}prev = ret->next;delete ret;return prev;}
};

代码思路

1. 定义小根堆的比较器：

   • 使用 struct cmp 定义一个小根堆的比较器，确保堆顶始终是最小的节点。

2. 初始化小根堆：

   • 创建一个优先队列 heap，用于存储所有链表的当前节点。

   • 将所有链表的头节点加入小根堆（如果链表不为空）。

3. 合并 K 个有序链表：

   • 创建一个虚拟头节点 ret，用于简化结果链表的构建。

   • 使用指针 prev 指向结果链表的最后一个节点。

   • 循环从堆中取出最小的节点 t，并将其连接到结果链表中。

   • 如果 t->next 不为空，将 t->next 加入小根堆。

   • 重复上述步骤，直到小根堆为空。

4. 返回结果链表：

   • 返回 ret->next，即合并后的有序链表的头节点。

   • 删除虚拟头节点 ret，释放内存。

---

举例说明

假设有以下 3 个有序链表：

• 链表 1：1 -> 4 -> 5

• 链表 2：1 -> 3 -> 4

• 链表 3：2 -> 6

初始状态

• 小根堆中包含所有链表的头节点：[1, 1, 2]。

执行过程

1. 第一次循环：

   • 取出堆顶节点 1（来自链表 1 或链表 2）。

   • 将 1 连接到结果链表。

   • 将 1->next（4 或 3）加入小根堆。

   • 堆状态：[1, 2, 3] 或 [1, 2, 4]。

2. 第二次循环：

   • 取出堆顶节点 1（来自另一个链表）。

   • 将 1 连接到结果链表。

   • 将 1->next（3 或 4）加入小根堆。

   • 堆状态：[2, 3, 4]。

3. 第三次循环：

   • 取出堆顶节点 2（来自链表 3）。

   • 将 2 连接到结果链表。

   • 将 2->next（6）加入小根堆。

   • 堆状态：[3, 4, 6]。

4. 第四次循环：

   • 取出堆顶节点 3（来自链表 2）。

   • 将 3 连接到结果链表。

   • 将 3->next（4）加入小根堆。

   • 堆状态：[4, 4, 6]。

5. 第五次循环：

   • 取出堆顶节点 4（来自链表 1 或链表 2）。

   • 将 4 连接到结果链表。

   • 将 4->next（5 或 nullptr）加入小根堆（如果存在）。

   • 堆状态：[4, 5, 6]。

6. 第六次循环：

   • 取出堆顶节点 4（来自另一个链表）。

   • 将 4 连接到结果链表。

   • 将 4->next（nullptr）不加入小根堆。

   • 堆状态：[5, 6]。

7. 第七次循环：

   • 取出堆顶节点 5（来自链表 1）。

   • 将 5 连接到结果链表。

   • 将 5->next（nullptr）不加入小根堆。

   • 堆状态：[6]。

8. 第八次循环：

   • 取出堆顶节点 6（来自链表 3）。

   • 将 6 连接到结果链表。

   • 堆为空，循环结束。

最终结果

• 合并后的链表为：1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6。

---

代码总结

1. 小根堆的作用：

   • 小根堆用于高效地找到当前最小的节点，确保每次都能将最小的节点连接到结果链表中。

2. 虚拟头节点的使用：

   • 虚拟头节点 ret 简化了结果链表的构建过程。

3. 时间复杂度：

   • 假设 K 是链表的数量，N 是所有链表的总节点数。

   • 每个节点被插入和弹出小根堆一次，时间复杂度为 O(N log K)。

4. 空间复杂度：

   • 小根堆最多存储 K 个节点，空间复杂度为 O(K)。

---

执行步骤总结

1. 将所有链表的头节点加入小根堆。

2. 循环从小根堆中取出最小节点，连接到结果链表。

3. 将取出的节点的下一个节点加入小根堆。

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* mergeKLists(vector<ListNode*>& lists) {return merge(lists, 0, lists.size() - 1);}ListNode* merge(vector<ListNode*>& lists, int left, int right) {if (left > right)return nullptr;if (left == right)return lists[left];// 1. 平分数组int mid = left + right >> 1;// [left, mid] [mid + 1, right]// 2. 递归处理左右区间ListNode* l1 = merge(lists, left, mid);ListNode* l2 = merge(lists, mid + 1, right);// 3. 合并两个有序链表return mergeTowList(l1, l2);}ListNode* mergeTowList(ListNode* l1, ListNode* l2) {if (l1 == nullptr)return l2;if (l2 == nullptr)return l1;// 合并两个有序链表ListNode head;ListNode *cur1 = l1, *cur2 = l2, *prev = &head;head.next = nullptr;while (cur1 && cur2) {if (cur1->val <= cur2->val) {prev = prev->next = cur1;cur1 = cur1->next;} else {prev = prev->next = cur2;cur2 = cur2->next;}}if (cur1)prev->next = cur1;if (cur2)prev->next = cur2;return head.next;}
};

代码分析

1. 类的结构

// 链表节点结构
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) {}
};

• ListNode 是单链表节点的定义，包含一个整数值 val 和指向下一个节点的指针 next。

2. 主函数 - mergeKLists

ListNode* mergeKLists(vector<ListNode*>& lists) {return merge(lists, 0, lists.size() - 1);
}

• mergeKLists 函数接受一个链表数组 lists，调用 merge 函数来合并这些链表，传入左边界和右边界（0 和 lists.size() - 1）。

3. 分治法 - merge

ListNode* merge(vector<ListNode*>& lists, int left, int right) {if (left > right)return nullptr; // 边界情况if (left == right)return lists[left]; // 只有一个链表时返回该链表

• merge 函数通过递归将链表数组分成两半，继续合并，直到每个子数组只包含一个链表。

• 如果 left 大于 right，则返回 nullptr；如果 left 等于 right，则返回对应的链表。

4. 平分数组与递归

int mid = left + right >> 1; // 平分数组
ListNode* l1 = merge(lists, left, mid); // 合并左半部分
ListNode* l2 = merge(lists, mid + 1, right); // 合并右半部分

• 使用索引 mid 将链表数组平分，分别递归调用 merge 函数处理左半部分和右半部分。

5. 合并两个有序链表 - mergeTowList

return mergeTowList(l1, l2);

• 在左右两部分排序完成后，调用 mergeTowList 函数合并这两个有序链表。

6. 合并过程

ListNode* mergeTowList(ListNode* l1, ListNode* l2) {if (l1 == nullptr)return l2; // 如果 l1 为空，返回 l2if (l2 == nullptr)return l1; // 如果 l2 为空，返回 l1

• mergeTowList 函数用于合并两个单独的有序链表。

• 首先处理边界情况，如果某个链表为空，直接返回另一个链表。

7. 合并逻辑

ListNode head;
ListNode *cur1 = l1, *cur2 = l2, *prev = &head;
head.next = nullptr;
while (cur1 && cur2) {if (cur1->val <= cur2->val) {prev = prev->next = cur1; // 将较小的节点加入合并链表cur1 = cur1->next;} else {prev = prev->next = cur2;cur2 = cur2->next;}
}

• 使用两个指针 cur1 和 cur2 遍历链表 l1 和 l2，通过比较值将较小的节点添加到新的合并链表中，并移动相应的指针。

• prev 指向合并后的链表的最后一个节点，初始时指向一个虚拟的头节点 head。

8. 处理剩余节点

if (cur1)prev->next = cur1; // 如果 l1 有剩余，连接到合并链表
if (cur2)prev->next = cur2; // 如果 l2 有剩余，连接到合并链表
return head.next; // 返回合并后的链表

• 如果 cur1 或 cur2 中还有未遍历的节点，将其连接到合并链表的末尾。

• 返回 head.next，即合并后链表的头节点。

举例说明

假设我们有三个链表如下：

• 链表 1: 1 -> 4 -> 5

• 链表 2: 1 -> 3 -> 4

• 链表 3: 2 -> 6

合并过程

1. 初始调用:

   mergeKLists([{1, 4, 5}, {1, 3, 4}, {2, 6}])
   

   • 调用 merge，此时 left = 0, right = 2，进行分割。

2. 第一次分割:

   • 中间索引 mid = 1。分为 [0, 1] 和 [2]。

   • 对 [0, 1] 继续分割。

3. 第二次分割:

   • 对 [0, 1]，中间索引 mid = 0，分为 [0] 和 [1]。

   • 递归返回链表 1 和链表 2。

4. 合并链表 1 和 链表 2:

   • 合并结果为: 1 -> 1 -> 3 -> 4 -> 4 -> 5。

5. 合并结果与链表 3:

   • 最后调用 mergeTowList 合并结果与链表 3。

   • 合并后的最终结果为: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6。

五、25. K 个一组翻转链表 - 力扣（LeetCode） 

算法代码： 

/*** 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* reverseKGroup(ListNode* head, int k) {// 1. 先求出需要逆序多少组int n = 0;ListNode* cur = head;while (cur) {cur = cur->next;n++;}n /= k;// 2. 重复 n 次：⻓度为 k 的链表的逆序即可ListNode* newHead = new ListNode(0);ListNode* prev = newHead;cur = head;for (int i = 0; i < n; i++) {ListNode* tmp = cur;for (int j = 0; j < k; j++) {ListNode* next = cur->next;cur->next = prev->next;prev->next = cur;cur = next;}prev = tmp;}// 把不需要翻转的接上prev->next = cur;cur = newHead->next;delete newHead;return cur;}
};

代码分析

1. 链表节点结构定义

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) {}
};

• ListNode 是单链表节点的定义，包含一个整数值 val 和指向下一个节点的指针 next。

2. 主函数 - reverseKGroup

ListNode* reverseKGroup(ListNode* head, int k) {// 1. 先求出需要逆序多少组int n = 0;ListNode* cur = head;while (cur) {cur = cur->next;n++;}n /= k; // 需要逆序的完整组数

• 该函数接受链表头节点 head 和一个整数 ( k ) 作为输入。

• 首先，计算链表的长度 ( n )，并通过 n /= k 计算需要逆序的完整组数。

3. 逆序过程

ListNode* newHead = new ListNode(0); // 创建一个虚拟头节点
ListNode* prev = newHead; // prev 指向新链表的尾部
cur = head; // cur 指向原链表的头
for (int i = 0; i < n; i++) {ListNode* tmp = cur; // 暂存当前组的头节点for (int j = 0; j < k; j++) {ListNode* next = cur->next; // 暂存下一个节点cur->next = prev->next; // 将当前节点插入到 prev 后面prev->next = cur; // 更新 prevcur = next; // 移动到下一个节点}prev = tmp; // 更新 prev 为当前组的头节点
}

• 创建一个虚拟头节点 newHead，方便处理链表的插入和返回。

• 使用 prev 指针来构建新的链表，初始时指向 newHead。

• 通过一个外层循环遍历需要逆序的组，每次逆序 ( k ) 个节点。

• 内层循环负责逆序当前 ( k ) 个节点。具体步骤为：

  • 暂存当前节点的下一个节点 next。

  • 将当前节点 cur 插入到 prev 后面，使得 cur 成为逆序链表的一部分。

  • 更新 cur 指向下一节点。

4. 处理不需要翻转的部分

// 把不需要翻转的接上
prev->next = cur;
cur = newHead->next; // 更新 cur 为新的头节点
delete newHead; // 删除虚拟头节点
return cur; // 返回新的头节点

• 当所有需要翻转的组都处理完后，将不需要翻转的部分直接连接到 prev 的后面。

• 更新 cur 为新链表的头节点，删除虚拟头节点 newHead，并返回链表的新头节点。

举例说明

假设有一个链表如下：

• 输入链表: 1 -> 2 -> 3 -> 4 -> 5

• k = 2

处理过程

1. 计算链表长度:

   • 链表长度 ( n = 5 )，计算得到 ( n / k = 2 )。因此，需要逆序 2 组。

2. 第一次逆序:

   • 当前节点 cur 指向 1，暂存为 tmp。

   • 逆序 2 个节点：

     • 1 -> 2 当前为: 2 -> 1 -> (后续)

     • 2 -> 3 更新: 1 -> 2 -> (后续)

     • 逆序后链表: 2 -> 1 (指向 3)

3. 第二次逆序:

   • cur 现在指向 3，暂存为 tmp。

   • 逆序 2 个节点：

     • 3 -> 4 当前为: 4 -> 3 -> (后续)

     • 3 -> 5 更新: 4 -> 3 -> (后续)

     • 逆序后链表: 4 -> 3 (指向 5)

4. 处理剩余节点:

   • 此时 cur 指向 5，prev 指向 3，将 5 直接连接到最后：

   • 最终链表为：2 -> 1 -> 4 -> 3 -> 5

总结

• 最终输出的链表是：2 -> 1 -> 4 -> 3 -> 5。

• 当链表的节点数不足 ( k ) 时（例如以下情况1 -> 2 -> 3 -> 4 -> 5 -> 6，当 ( k = 4 ) 时），只会逆序前 4 个节点，后面的节点保持原顺序，结果为：4 -> 3 -> 2 -> 1 -> 5 -> 6。