LeetCode 25. K 个一组翻转链表(***)
题目类型
- 链表
- k组翻转
题目链接
思路
此时看起来不难,实际实现的时候很容易出错,建议多刷几次
- 每次检验是否下一组足够k个元素,不够则break 够的话继续往下执行
- 对于 p->a->b->c->d 从a开始进行k-1次循环反转指针,而且注意在反转指针之前要把b->next存起来
auto c = b->next, b->next = a
- k-1次之后(也就是该组已经反转成功后) 此时将p->next->next = b,落到了下一组以b为开始的反转的前一个结点(可以看做是虚拟结点)
- 继续以上操作
AC代码
/**
* 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) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
for (auto p = dummy;;)
{
// 判断是否满足k个元素
auto q = p;
for (int i = 0; i < k && q; i ++) q = q->next;
if (!q) break; // 不满足直接跳出
// 满足有k个元素
auto a = p->next, b = a->next;
for (int i = 0; i < k - 1; i ++) // 内部交换k - 1次
{
auto c = b->next;
b->next = a;
a = b, b = c;
}
auto t = p->next;
p->next = a;
t->next = b;
p = t;
}
return dummy->next;
}
};