# 20-line iterative C++ solution

• ``````-1 -> 1 -> 2 -> 3 -> 4 -> 5
|    |    |    |
pre  cur  nex  tmp

-1 -> 2 -> 1 -> 3 -> 4 -> 5
|         |    |    |
pre       cur  nex  tmp

-1 -> 3 -> 2 -> 1 -> 4 -> 5
|              |    |    |
pre            cur  nex  tmp
``````

Above is how it works inside one group iteration(for example, k=3)

``````class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
int num=0;
while(cur = cur->next)
num++;
while(num>=k) {
cur = pre->next;
nex = cur->next;
for(int i=1;i<k;i++) {
tmp= nex->next;
nex->next = pre->next;
pre->next = nex;
cur->next = tmp;
nex = tmp;
}
pre = cur;
num-=k;
}
}
};
``````

Thanks to ciaoliang1992, the tmp pointer is no necessary, so the more concise solution is

``````class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
int num=0;
while(cur = cur->next)
num++;
while(num>=k) {
cur = pre->next;
nex = cur->next;
for(int i=1;i<k;++i) {
cur->next=nex->next;
nex->next=pre->next;
pre->next=nex;
nex=cur->next;
}
pre = cur;
num-=k;
}
}
};``````

• very good code.
But i think the ListNode *temp isn't necessary.
You can change the loop:

``````        cur=pre->next;
next=cur->next;
for(int i=1;i<k;++i){
cur->next=next->next;
next->next=pre->next;
pre->next=next;
next=cur->next;
}
pre = cur;``````

• Very nice code , but shouldn`t you memory of the 'preheader' ?

• Ye you are right. I should delete the preheader. But I prefer smart pointer to do this, which is infeasible here so I just leave it there. (I don't like save it to a variable and delete it... I know I'm kind of paranoid on this...)

• To not leak memory and to not have to delete `preheader` manually, you could just do this:

``````    ListNode preheader(-1);
.
.
.
``````

• great thanks!!! I was wandering about it for a long time . Enlightened by your code!!!

``````class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
int n=0;
while(n>=k){
for(int i=1;i<k;i++){
end=start->next;
start->next=end->next;
end->next=pre->next;
pre->next=end;
}
pre=start;
start=pre->next;
n-=k;
}
}
};``````

• There's no need for the dummy head if a 'pointer to the pointer' is used. Plus we can avoid checking the remaining length (which effectively causes the list to be traversed twice instead of once) by simply reversing the last segment back when the end is reached:

``````class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if( k > 1 ) for(auto pp=&head; *pp;) pp = reverse(pp, k);
}
private:
ListNode** reverse(ListNode** pphead, int k) {
for(int kr=1; kr<k; kr++) {
if( ! *ppnew ) return reverse(pphead, kr);
auto pnext = (*ppnew)->next;
*ppnew = pnext;
}
return ppnew;
}
};``````

• class Solution {

``````    public:
ListNode* reverseKGroup(ListNode* head, int k) {

int n=0;
while(p1)
{
p1=p1->next;
n++;
}
n=n/k;
for(int i=0;i<n;i++)
{
ListNode *prev=NULL,*next=NULL;
int l=1;
p1=cur;
while(l++<=k)
{
next=cur->next;
cur->next=prev;
prev=cur;
cur=next;
}
if(i>=1)
first->next=prev;
else
p2=prev;
first=p1;
}
first->next=cur;
return p2;
}
};``````

• Using stack to simplify the pointer operation,extra space is k* sizeof(ListNode*) ,it is constant.

``````	ListNode* reverseKGroup(ListNode* head, int k) {
stack<ListNode*>stack1;
int m = k, num = 0;
ListNode* p = head, dummy(0), *pcur = &dummy;
while (p) {
++num;
p = p->next;
}
while (num >= k) {
m = k;
while (m--) {
stack1.push(p);
p = p->next;
}
m = k;
while (m--) {
pcur->next = stack1.top();
stack1.pop();
pcur = pcur->next;
pcur->next = NULL;
}
num -= k;
}
if (p) pcur->next = p;
return dummy.next;
}
``````

• ``````ListNode* reverseKGroup(ListNode* head, int k) {
while(1){
LNptp2=LNptp;
vector<int> vi;
int i=0;
for(i=0;i<k;i++){
if(LNptp==NULL) break;
vi.push_back(LNptp->val);
LNptp=LNptp->next;
}
if(i<k) break;
for(i=k-1;i>=0;i--){
LNptp2->val=vi[i];
LNptp2=LNptp2->next;
}
}
}
``````

• My Java version of the same. Hope it helps.

``````public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy , nex = dummy, pre = dummy;
int count = 0;
while(cur.next != null){
cur = cur.next;
count++;
}
while(count >= k){
cur = pre.next;
nex = cur.next;
for(int i = 1; i < k; i++){
cur.next = nex.next;
nex.next = pre.next;
pre.next = nex;
nex = cur.next;
}
pre = cur;
count-=k;
}
return dummy.next;
}
}
``````

• My C++ Solution.

``````ListNode* reverseKGroup(ListNode* head, int k) {
int n=0;
ListNode* cur=head, *tmp=0, *previous =0, *next =0, *lastTail=0, *previousTail=0;
if (head == 0 || k <= 1)
while (cur != 0)
{
n++;
cur = cur->next;
}
int groups = n / k;
previous = 0;
for (int i = 0; i < groups; i++)
{
lastTail = 0;
for (int j = 0; j < k; j++)
{
next = cur->next;
cur->next = previous;
previous = cur;
if (lastTail == 0)
{
lastTail = cur;
}
cur = next;
}
{
}
if (previousTail != 0)
previousTail->next = previous;
previousTail = lastTail;
}
if (n>k)
lastTail->next = cur;