O(n) and O(1) of course it is.

Each time when starting, find the future new head (nh) and save the old head of the next to-be-reversed list. If existed, nh is k step far from oh. Then reverse the list from oh to nh and save its tail for combination.

Example:

1-2-3-4-5

iter1: oh = 1, nh = 2 2-1-3-4-5

iter2: oh = 3, nh = 4 2-1-4-3-5

iter3: oh = 5, nh = 0 2-1-4-3-5

```
ListNode *reverseKGroup(ListNode *head, int k) {
if(!head || !head->next || k==1) return head;
int i=k;
ListNode * p0 = head, * p1 = head->next, * p2 = 0, * t = 0, * ret = head, *oh, * nh;
while(p1)
{
oh = nh = p0;
i = k;
while(--i && nh)
nh = nh->next;
if(!nh) break;
i = k;
while(--i)
{
p2 = p1->next;
p1->next = p0;
p0 = p1;
p1 = p2;
}
if(t)
t->next = p0;
else
ret = p0;
p0 = oh;
t = p0;
p0 = p0->next = p1;
if(p1)
p1 = p1->next;
}
return ret;
}
```