# K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
- 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
- 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
示例 3：
输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]
示例 4：
输入：head = [1], k = 1
输出：[1]
提示：
- 列表中节点的数量在范围
sz 内 1 <= sz <= 50000 <= Node.val <= 10001 <= k <= sz
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
- 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
- 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
示例 3：
输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]
示例 4：
输入：head = [1], k = 1
输出：[1]
提示：
- 列表中节点的数量在范围
sz 内 1 <= sz <= 50000 <= Node.val <= 10001 <= k <= sz
以下错误的选项是？
## aop
### before
```cpp
struct ListNode
{
int val;
struct ListNode *next;
ListNode() : val(0), next(nullptr){};
ListNode(int x) : val(x), next(nullptr){};
ListNode(int x, ListNode *next) : val(x), next(next){};
};
```
### after
```cpp
```
## 答案
```cpp
class Solution
{
public:
ListNode *reverseKGroup(ListNode *head, int k)
{
if (head == NULL || head->next == NULL || k == 1)
return head;
ListNode *cur = head;
int i = 1;
while (cur->next != NULL)
{
cur = cur->next;
}
if (i < k)
return head;
stack s;
ListNode *p = head;
while (s.size() != k)
{
s.push(p);
p = p->next;
}
ListNode *phead = s.top();
s.pop();
ListNode *p2 = phead;
while (!s.empty())
{
p2->next = s.top();
s.pop();
p2 = p2->next;
p2->next = NULL;
}
while (p != NULL)
{
s.push(p);
p = p->next;
if (s.size() == k)
{
while (!s.empty())
{
p2->next = s.top();
s.pop();
p2 = p2->next;
p2->next = NULL;
}
}
}
if (!s.empty())
{
stack s2;
while (!s.empty())
{
s2.push(s.top());
s.pop();
}
while (!s2.empty())
{
p2->next = s2.top();
s2.pop();
p2 = p2->next;
}
}
return phead;
}
};
```
## 选项
### A
```cpp
class Solution
{
public:
vector reverse(ListNode *head, int k)
{
ListNode *newhead = NULL;
vector res;
res.push_back(head);
int i = 0;
ListNode *head1 = head;
while (head1)
{
i++;
head1 = head1->next;
if (i == k)
{
break;
}
}
if (i < k)
{
return res;
}
while (k)
{
ListNode *nexthead = head->next;
head->next = newhead;
newhead = head;
head = nexthead;
k--;
}
res.push_back(newhead);
res.push_back(head);
return res;
}
ListNode *reverseKGroup(ListNode *head, int k)
{
ListNode *newhead = new ListNode(0);
ListNode *tmp = newhead;
while (head)
{
vector res = reverse(head, k);
if (res.size() == 3)
{
tmp->next = res[1];
tmp = res[0];
head = res[2];
}
else
{
tmp->next = res[0];
head = NULL;
}
}
return newhead->next;
}
};
```
### B
```cpp
class Solution
{
public:
ListNode *reverseK(ListNode *pre, ListNode *lat)
{
ListNode *lpre = pre->next;
ListNode *cur = lpre->next;
while (cur != lat)
{
lpre->next = cur->next;
cur->next = pre->next;
pre->next = cur;
cur = lpre->next;
}
return lpre;
}
ListNode *reverseKGroup(ListNode *head, int k)
{
ListNode *h = new ListNode(-1);
h->next = head;
ListNode *cur = head;
int t = 1;
ListNode *pre = h;
while (cur != NULL)
{
if (t % k == 0)
{
pre = reverseK(pre, cur->next);
cur = pre->next;
}
else
cur = cur->next;
t += 1;
}
return h->next;
}
};
```
### C
```cpp
class Solution
{
public:
ListNode *reverseKGroup(ListNode *head, int k)
{
int len = 0;
struct ListNode dummy, *prev = &dummy;
dummy.next = head;
for (; head != nullptr; head = head->next)
{
if (++len % k == 0)
{
struct ListNode *p = prev->next;
while (prev->next != head)
{
struct ListNode *q = p->next;
p->next = q->next;
q->next = prev->next;
prev->next = q;
}
prev = p;
head = p;
}
}
return dummy.next;
}
};
```