k个一组反转链表。本题中链表至少有1个节点，k保证是有效的，即1<=k<=n。
只考虑O(1)存储空间的办法的话，比较容易想到的就是，每数到k个节点就返回去反转这k个节点。不能边数边反转的原因是：不能确定后面还够不够k个节点，如果不够k个节点的话是不用反转的。
假设已经有了反转k个节点的子函数，那么整个过程就可以这样处理：每k个一组的链表反转以后，要得到反转后的链表段的head和tail，设当前的head和tail分别为this_head和this_tail，然后把上一个tail连着这一个head，即last_tail->next = this_head，再更新tail值为this_tail，即last_tail = this_tail，这样就能把整个链表都串起来了。
下面考虑reverseList的子函数应该怎么写，受反转单链表那道题(LeetCode206)的启发，那道题的递归解法就是找到了每一个子问题的tail和head，tail就是反转前的第一个节点，迭代时可以很容易地得到，head就是子问题返回的节点，把这个思想稍作修改，就能得到这道题里面的子函数。整体代码如下：
/** * 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) { if(!head->next || 1 == k) return head; //初始化start，tail。为了tail的初始值，要申请一个新节点作为head之前的节点 ListNode* p = head, *start = head; ListNode* pre = new ListNode(0); ListNode* tail = pre; int cnt = 0; while(p) { ++cnt; ListNode* nex = p->next; //当找到k个节点后，反转这k个节点，并将上一个tail连向这一个头，然后更新tail和start if(cnt == k) { tail->next = reverse(start, k); tail = start; cnt = 0; start = nex; } p = nex; } if(cnt != 0) tail->next = start; //后面可能还有不足k个的节点，要注意这部分的连接 return pre->next; } private: //反转从start开始的k个节点，返回反转后的头节点指针 ListNode* reverse(ListNode* start, int k) { //本题能保证start开始一定存在k个节点，所以该函数中不需要考虑边界情况 int cnt = 1; ListNode *p = start->next; start->next = nullptr; while(p) { ListNode* nex = p->next; p->next = start; start = p; p = nex; ++cnt; if(cnt == k) break; } return start; } };
