链表（典型算法思想）—— 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
按照代码的逻辑，相加过程如下：
-
初始化:
-
cur1指向2，cur2指向5。 -
newhead是一个虚拟头节点，prev指向newhead。 -
t = 0。
-
-
第一次循环:
-
t = 0 + 2 + 5 = 7。 -
创建新节点
7，prev->next指向7，prev指向7。 -
t = 7 / 10 = 0。 -
cur1指向4，cur2指向6。
-
-
第二次循环:
-
t = 0 + 4 + 6 = 10。 -
创建新节点
0，prev->next指向0，prev指向0。 -
t = 10 / 10 = 1。 -
cur1指向3，cur2指向4。
-
-
第三次循环:
-
t = 1 + 3 + 4 = 8。 -
创建新节点
8，prev->next指向8，prev指向8。 -
t = 8 / 10 = 0。 -
cur1和cur2都为nullptr，循环结束。
-
-
返回结果:
-
结果链表为
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;
}
};代码思路
-
检查边界条件：
-
如果链表为空（
head == nullptr）或只有一个节点（head->next == nullptr），直接返回head，因为不需要交换。
-
-
创建虚拟头节点：
-
创建一个虚拟头节点
newHead，并将其next指向链表的头节点head。虚拟头节点的作用是简化头节点的交换操作，避免特殊处理。
-
-
初始化指针：
-
prev：指向当前节点对的前一个节点（初始为newHead）。 -
cur：指向当前节点对中的第一个节点（初始为head）。 -
next：指向当前节点对中的第二个节点（初始为cur->next）。 -
nnext：指向next的下一个节点（初始为next->next）。
-
-
遍历链表并交换节点：
-
使用
while循环遍历链表，直到cur或next为空。 -
在循环中：
-
交换节点：
-
将
prev->next指向next。 -
将
next->next指向cur。 -
将
cur->next指向nnext。
-
-
更新指针：
-
将
prev指向cur（当前节点对中的第一个节点）。 -
将
cur指向nnext。 -
如果
cur不为空，将next指向cur->next。 -
如果
next不为空，将nnext指向next->next。
-
-
-
-
返回结果：
-
将
cur指向newHead->next（交换后的链表头节点）。 -
删除虚拟头节点
newHead，释放内存。 -
返回
cur（交换后的链表）。
-
举例说明
假设链表为 1 -> 2 -> 3 -> 4，交换过程如下：
初始状态
-
newHead -> 1 -> 2 -> 3 -> 4 -
prev = newHead -
cur = 1 -
next = 2 -
nnext = 3
第一次交换
-
交换节点：
-
prev->next指向2。 -
next->next指向1。 -
cur->next指向3。
-
-
更新指针：
-
prev = 1。 -
cur = 3。 -
next = 4。 -
nnext = nullptr（因为next->next为空）。
-
第二次交换
-
交换节点：
-
prev->next指向4。 -
next->next指向3。 -
cur->next指向nullptr。
-
-
更新指针：
-
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;
}
};代码思路
-
处理边界情况：
-
如果链表为空（
head == nullptr）、只有一个节点（head->next == nullptr）或只有两个节点（head->next->next == nullptr），直接返回，因为不需要重排。
-
-
找到链表的中间节点：
-
使用 快慢双指针：
-
slow指针每次移动一步。 -
fast指针每次移动两步。
-
-
当
fast到达链表末尾时，slow指向链表的中间节点。 -
将链表从中间节点断开，分为前半部分和后半部分。
-
-
逆序后半部分链表：
-
使用 头插法 将后半部分链表逆序：
-
创建一个虚拟头节点
head2。 -
遍历后半部分链表，将每个节点插入到
head2的后面。
-
-
最终，
head2->next指向逆序后的后半部分链表。
-
-
合并两个链表：
-
使用 双指针 将前半部分链表和逆序后的后半部分链表合并：
-
cur1指向前半部分链表的头节点。 -
cur2指向逆序后的后半部分链表的头节点。 -
依次交替连接两个链表的节点。
-
-
最终，链表被重排为所需顺序。
-
-
释放临时节点：
-
删除虚拟头节点
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。
代码总结
-
快慢双指针：
-
用于找到链表的中间节点，确保链表被正确分为两部分。
-
-
头插法逆序链表：
-
将后半部分链表逆序，便于后续合并。
-
-
双指针合并链表：
-
交替连接两个链表的节点，完成重排。
-
-
边界条件处理：
-
确保代码在链表节点数较少时也能正常运行。
-
执行步骤总结
-
找到中间节点并断开链表。
-
逆序后半部分链表。
-
合并前半部分和逆序后的后半部分链表。
-
释放临时节点，返回重排后的链表。
四、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;
}
};代码思路
-
定义小根堆的比较器：
-
使用
struct cmp定义一个小根堆的比较器，确保堆顶始终是最小的节点。
-
-
初始化小根堆：
-
创建一个优先队列
heap，用于存储所有链表的当前节点。 -
将所有链表的头节点加入小根堆（如果链表不为空）。
-
-
合并 K 个有序链表：
-
创建一个虚拟头节点
ret，用于简化结果链表的构建。 -
使用指针
prev指向结果链表的最后一个节点。 -
循环从堆中取出最小的节点
t，并将其连接到结果链表中。 -
如果
t->next不为空，将t->next加入小根堆。 -
重复上述步骤，直到小根堆为空。
-
-
返回结果链表：
-
返回
ret->next，即合并后的有序链表的头节点。 -
删除虚拟头节点
ret，释放内存。
-
举例说明
假设有以下 3 个有序链表：
-
链表 1：
1 -> 4 -> 5 -
链表 2：
1 -> 3 -> 4 -
链表 3：
2 -> 6
初始状态
-
小根堆中包含所有链表的头节点：
[1, 1, 2]。
执行过程
-
第一次循环：
-
取出堆顶节点
1（来自链表 1 或链表 2）。 -
将
1连接到结果链表。 -
将
1->next（4或3）加入小根堆。 -
堆状态：
[1, 2, 3]或[1, 2, 4]。
-
-
第二次循环：
-
取出堆顶节点
1（来自另一个链表）。 -
将
1连接到结果链表。 -
将
1->next（3或4）加入小根堆。 -
堆状态：
[2, 3, 4]。
-
-
第三次循环：
-
取出堆顶节点
2（来自链表 3）。 -
将
2连接到结果链表。 -
将
2->next（6）加入小根堆。 -
堆状态：
[3, 4, 6]。
-
-
第四次循环：
-
取出堆顶节点
3（来自链表 2）。 -
将
3连接到结果链表。 -
将
3->next（4）加入小根堆。 -
堆状态：
[4, 4, 6]。
-
-
第五次循环：
-
取出堆顶节点
4（来自链表 1 或链表 2）。 -
将
4连接到结果链表。 -
将
4->next（5或nullptr）加入小根堆（如果存在）。 -
堆状态：
[4, 5, 6]。
-
-
第六次循环：
-
取出堆顶节点
4（来自另一个链表）。 -
将
4连接到结果链表。 -
将
4->next（nullptr）不加入小根堆。 -
堆状态：
[5, 6]。
-
-
第七次循环：
-
取出堆顶节点
5（来自链表 1）。 -
将
5连接到结果链表。 -
将
5->next（nullptr）不加入小根堆。 -
堆状态：
[6]。
-
-
第八次循环：
-
取出堆顶节点
6（来自链表 3）。 -
将
6连接到结果链表。 -
堆为空，循环结束。
-
最终结果
-
合并后的链表为：
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6。
代码总结
-
小根堆的作用：
-
小根堆用于高效地找到当前最小的节点，确保每次都能将最小的节点连接到结果链表中。
-
-
虚拟头节点的使用：
-
虚拟头节点
ret简化了结果链表的构建过程。
-
-
时间复杂度：
-
假设 K 是链表的数量，N 是所有链表的总节点数。
-
每个节点被插入和弹出小根堆一次，时间复杂度为
O(N log K)。
-
-
空间复杂度：
-
小根堆最多存储 K 个节点，空间复杂度为
O(K)。
-
执行步骤总结
-
将所有链表的头节点加入小根堆。
-
循环从小根堆中取出最小节点，连接到结果链表。
-
将取出的节点的下一个节点加入小根堆。
-
重复上述步骤，直到小根堆为空。
-
返回合并后的有序链表。
解法二：算法代码（递归/分治）
/**
* 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 为空，返回 l2
if (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
合并过程
-
初始调用:
mergeKLists([{1, 4, 5}, {1, 3, 4}, {2, 6}])-
调用
merge，此时left = 0,right = 2，进行分割。
-
-
第一次分割:
-
中间索引
mid = 1。分为[0, 1]和[2]。 -
对
[0, 1]继续分割。
-
-
第二次分割:
-
对
[0, 1]，中间索引mid = 0，分为[0]和[1]。 -
递归返回链表 1 和链表 2。
-
-
合并链表 1 和 链表 2:
-
合并结果为: 1 -> 1 -> 3 -> 4 -> 4 -> 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; // 更新 prev
cur = 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
处理过程
-
计算链表长度:
-
链表长度 ( n = 5 )，计算得到 ( n / k = 2 )。因此，需要逆序 2 组。
-
-
第一次逆序:
-
当前节点
cur指向 1，暂存为tmp。 -
逆序 2 个节点：
-
1 -> 2 当前为: 2 -> 1 -> (后续)
-
2 -> 3 更新: 1 -> 2 -> (后续)
-
逆序后链表: 2 -> 1 (指向 3)
-
-
-
第二次逆序:
-
cur现在指向 3，暂存为tmp。 -
逆序 2 个节点：
-
3 -> 4 当前为: 4 -> 3 -> (后续)
-
3 -> 5 更新: 4 -> 3 -> (后续)
-
逆序后链表: 4 -> 3 (指向 5)
-
-
-
处理剩余节点:
-
此时
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。