晨起开门雪满山
雪睛云淡日光寒
链表题，这个题目第一次遇到是在PAT甲级的题库中，还记得当初刷过两遍的PAT甲级。。。
题目其实蛮简单，大部分人其实都做过链表的翻转，头插法或者尾插法。这道题也一样，按照K个分组进行尾插法或者头插法翻转每个分组的链表。
稍微麻烦点就是要维护每次翻转后的分组链表的尾巴。。。就这么简单。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
ListNode *reverse(ListNode *prev, int k) {
ListNode *end = prev->next;
ListNode *next = end->next;
for (int i = 0; i < k - 1; i++) {
ListNode *temp_next = next->next;
next->next = prev->next;
prev->next = next;
next = temp_next;
}
end->next = next;
return end;
}
int length(ListNode *p) {
int len = 0;
while (p) {
len++;
p = p->next;
}
return len;
}
public:
ListNode* reverseKGroup(ListNode *head, int k) {
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *prev = dummy;
int len = length(head);
for (int i = 0; i < len / k; i++) {
prev = reverse(prev, k);
}
return dummy->next;
}
};
