描述
在一个单链表中，把单链表中的节点以k个节点为一组进行逆转。如果链表的节点个数不是k的倍数，则剩下的节点以原来的方式链接。
不可以改变节点的值，只能改变节点。
例如，对于链表1->2->3->4->5：
- k = 2，返回：2->1->4->3->5
- k = 3，返回：3->2->1->4->5
分析
1）从原始数组中取出k个节点；
2）第一步中获取到k个节点则逆置，逆置后的链表链接到结果链表中；不足k个节点，则将原始的链表链接到结果链表的尾部；
本题实现的核心点为原地逆转单链表。
实现
//Reverse Nodes In K-Group
ListNode *reverseNodesInKgroup(ListNode *head, int k)
{
if (head == nullptr || head->next == nullptr || k < 2) return head;
ListNode dummy(-1);
dummy.next = head;
for(ListNode *prev = &dummy, *end = head; end; end = prev->next) {
for (int i = 1; i < k && end; i++)
end = end->next;
if (end == nullptr) break; // 不足 k 个
prev = reverse(prev, prev->next, end);
}
return dummy.next;
}
ListNode* reverse(ListNode *prev, ListNode *begin, ListNode *end) {
ListNode *end_next = end->next;
for (ListNode *p = begin, *cur = p->next, *next = cur->next;
cur != end_next;
p = cur, cur = next, next = next ? next->next : nullptr) {
cur->next = p;
}
begin->next = end_next;
prev->next = end;
return begin;
}
时间复杂度为O(n)，空间复度为O(1)。
