描述
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
数据范围： \ 0 \le n \le 2000 0≤n≤2000 ， 1 \le k \le 20001≤k≤2000 ，链表中每个元素都满足 0 \le val \le 10000≤val≤1000
要求空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
例如：
给定的链表是 1\to2\to3\to4\to51→2→3→4→5
对于 k = 2k=2 , 你应该返回 2\to 1\to 4\to 3\to 52→1→4→3→5
对于 k = 3k=3 , 你应该返回 3\to2 \to1 \to 4\to 53→2→1→4→5
本题已AC
解题思路:
拿到这题，一个想法就是用栈来写。至于为什么我会想到用栈呢？因为需要反向嘛，这里我看题目的要求，空间复杂度为 O(1)。第一个想法是保存值，通过 new一个新的节点了实现。但是仔细一想，好像不可以的，因为这样空间复杂度肯定不符合，突然灵机一动，我们可以用栈保存节点是指针，nice.
1→2→3→4→5 k = 2时
1→2→3→4→5 k = 3时
4和5是不用翻转的，所以如果用栈又会带来一个问题，因为栈结构是先进后出的，如果用栈来保存肯定会导致，4，5也会被翻转。
这里有两个解决方法，
1.把4，5再次入栈(入另一个栈)，然后再输出 ok
2.不妨我们不使用栈结构，我们使用双向队列(而且双向队列在前后两端进行插入删除的效率也挺高的，所以我们使用这个结构最佳了)
我们哪一个例子来看：
1→2→3→4→5 k = 3时
准备工作，一个指向该链表的指针 head。一个deque,一个中间变量 tmpk
一些方便操作的辅助指针 s和ans
这里我们做一个循环，while(head != nullptr) 是的，一次遍历就可以搞定
此时退出循环，okk
判断 que是否为空或者tmpk是否等于 0
如果que不为空的话，说明que此时的节点是不需要翻转的
所以
那么这题就ok了,当然题目有一些细节，这个只能根据实际的测试清空来修改了
比如 {},2 {1,2},3 {1},2等
附上我通过的代码:
class Solution { public: /** * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ ListNode* reverseKGroup(ListNode* head, int k) { // write code here deque<ListNode*> sta; int tmpk = k; ListNode *s = nullptr; ListNode *ans = nullptr; while(head != nullptr) { sta.push_back(head); head = head->next; tmpk--; if(tmpk == 0) { if(s == nullptr) { s = sta.back(); sta.pop_back(); ans = s; } while(!sta.empty()) { s->next = sta.back(); sta.pop_back(); s = s->next; } tmpk = k; } } while(!sta.empty()) { if(s == nullptr) { s = sta.front(); sta.pop_front(); ans = s; } else { s->next = sta.front(); sta.pop_front(); s= s->next; } } if(s != nullptr) s->next = nullptr; return ans; } };
