LeetCode #25

# Description:

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

## Example:

``````For example,

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5
``````

# Idea:

k个group一起reverse，reverse的时候用到三个指针，前一个，头，尾。 `reverseList(ListNode *before, ListNode* begin, ListNode* end)`

# Code:

``````class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummy(-1);
ListNode *pre=&dummy;
while(end!=NULL){
for(int i=1; i<k && end!=NULL; ++i){
end=end->next;
}
if(end==NULL) break;
pre=reverseList(pre, pre->next, end);
end=pre->next;
}
return dummy.next;
}

ListNode* reverseList(ListNode *before, ListNode* begin, ListNode* end) {
ListNode *end_next=end->next; // 千万要存这个！不要直接用end->next!
ListNode *pre=end_next, *curr=begin;
ListNode *tmp;

while(curr!=end_next){
tmp = curr->next;
curr->next=pre;
pre=curr;
curr=tmp;
}
before->next=pre;
return begin;

}
};
``````