## Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified 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.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

### Analysis:

First consider the atomic operation in this problem: reverse several nodes.
How to reverse? Let's take an example, we have linked list 3->2->1->4->5->6->7
We wan to reverse 4->5->6 to 6->5->4, so we do the following:
(1) 3->2->1->4->5->6->7
p              q
(2) 3->2->1----->5->6->4->7
p             q
(3) 3->2->1--------->6->5->4->7
p             q

The 1st step is to find the locations q and q, where we want to reverse from p->next to q.
Then while p->next != q,  we do:
(1) move p->next to q->next
(2) connect p->next to p->next->next
Note that, p and q are fixed.

Now we solve this reverse problem, the final step is to scan the whole list:
When we finished one reverse, put p k steps further, set q=p, then put q k steps further to find the end node for the new reverse, if meet the end, no more reverse needed, return the list.

### Code(C++):

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
ListNode* p=new ListNode(0);
ListNode* q=p;
while (true){
int i=0;
while (q && i<k){q=q->next;i++;}
else{
while (p->next!=q){
ListNode* d = p->next;
ListNode* l = q->next;
p->next=p->next->next;
q->next=d;
d->next=l;
}
for(int j=0;j<k;j++){p=p->next;}
q=p;
}
}
}
};

### Code(Python):

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @param head, a ListNode
# @param k, an integer
# @return a ListNode
def reverseKGroup(self, head, k):
p = ListNode(0)
q = p
while True:
i = 0
while i < k and q != None:
q = q.next
i = i + 1
if q == None:
while p.next != q:
tmp1 = p.next
tmp2 = q.next
p.next = p.next.next
q.next = tmp1
q.next.next = tmp2

for j in xrange(k):
p = p.next
q = p



Old Version:

Analysis:

The idea is to scan from the 1st node to the last, if there are k nodes, then swap them, and count again, until get the end.

In order to swap k nodes, we can have
(1) The previous node, to link the previous list.  (pre)
(2) The 1st node to swap.   (st)
(3) The kth node to swap.  (ed)

The idea is to insert the current 1st node behind the end node.
e.g.
1->2->3->4->null, when k=4

(1)2->3->4->1->null
ed
(2)3->4->2->1->null
ed
(3)4->3->2->1->null
ed

After this swap, do not forget link the swapped list to the previous list.

Code:
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
ListNode* pre=new ListNode(0);
pre->next=p;
int c=0;
ListNode* st;
ListNode* ed;

while(p!=NULL){
c++;
if (c==1){st = p;} //get start node of every k nodes
if (c==k){
ed = p;         // get end node of every k nodes
ListNode *last=ed;  //store the list after the k nodes
ListNode *nst=st;   //store the next node to be reversed
while (st!=ed){     // reverse the k nodes
last = ed->next;
nst = st->next;
st->next = last;
ed->next = st;
st=nst;
}
pre->next = st;     //link to the previous list
for (int i=0;i<k-1;i++){    //get the end of the k nodes
p=p->next;
}
c=0;                //reset count = 0
}
if (c==0){pre = p;}     //store the previous list
p=p->next;              //go next nodes
}