问题描述：将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表，如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样你不能更改节点中的值，只能更改节点本身。

数据范围：  0≤n≤2000 ， 1≤k≤2000 ，链表中每个元素都满足 0≤val≤1000
要求空间复杂度 O(1)，时间复杂度 O(n)。例：给定单链表：1→2→3→4→5
对于 k=2 , 你应该返回2→1→4→3→5；
对于k =3 , 你应该返回3→2→1→4→5
问题首先想到的肯定是反转链表，但是这个题目是给定任意k，
那么每次反转就需要知道反转开始的节点和反转结束的节点。如何找到开始节点和结束节点很容易。
假设我们所设计的函数是reverse(ListNode*start,ListNode* end),
但是会碰到上一次反转后，这次反转出现如下问题：
1：以k=4为例：1->2->3->4->5->6->7->8->9->10.做完一次反转为：4->3->2->1->5->6->7->8->9->10.那么返回值不管是
指向1的指针还是指向5的指针，势必下一次的开始节点是一定是5，那么第二次的反转起始点就是5~8，那么结果会是什么呢？
第二次反转后的结果是：4->3->2->1  8->7->6->5->9->10.可以发现1和8没有链接是断开的。
2：整个函数应该反回什么值呢，k是任意的，链表长度是任意的，总不能人为的遍历一遍链表，让头节点指向第一个反转结束的地方。
所以我们接下来就是怎么解决这种断开的问题，和函数返回值问题。
我们可以想到开始节点的前驱，也就是设计函数：reverse(ListNode* pre,ListNode* start,ListNode* end);
每次反转结束后让pre->next=end.就可以解决像1——8断开链接的问题。
那么又会出现一个问题，第一次没有前驱怎么办，我们可以人为的新建一个链表头节点Nhead，使Nhead->next=head。
这样不管k如何变化，函数最后返回Nhead->next.就是新链表的头节点。
还有另外一个问题，我们设计的reverse函数应该返回哪个值，通过观察发现，第二次的start的前驱应该是1，所以我们reverse函数的
返回值应该是指向1节点的指针也就是第一次的start节点。然后每次反转时，让新的pre=上一个的start也就是调用reverse函数时的返回值。
这样就完美的解决了所有问题。
时间复杂度分析，假设整个链表长度为n，那么就有n/k组，每组需要操作的复杂度是k，所以整个函数的时间复杂度就是O(n).
空间复杂度为O(1),有限个变量。 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k==1) return head;
        if(head==NULL||head->next==NULL) return head;
        ListNode *Nhead=(ListNode*)malloc(sizeof(ListNode));
        Nhead->next=head;
        ListNode* pre=Nhead;
        ListNode *p,*q;
        p=head,q=head;
        int num=1;
        while(q!=NULL) {
            while(num<=k-1&&q!=NULL) q=q->next,++num;
            if(num==k&&q!=NULL) {
                pre=reverse(pre,p,q);
                p=pre->next;
                q=p;
                num=1;
            }
        }
        return Nhead->next;
    }
    ListNode* reverse(ListNode* pre,ListNode* start,ListNode* end) {
        ListNode* p=start;
        ListNode* q=end->next;;
        ListNode* tmp=q;
        while(start!=q){
            p=start;
            start=start->next;
            p->next=tmp;
            tmp=p;
        }
        q=pre->next;
        pre->next=p;
        return q;
    }
};