**Solution1. Non-Recursive Solution - Special thanks for StefanPochmann's comment**

```
Assuming we have a linkedList: A..B..C..D:
Say A..B is a k-Group,
We need 3 steps to reverse the k-Group:
1) Find the kth node B (tail)
2) B..A C..D: reverse A..B to B..A
3) B..A..C..D: connect the new tail A with the next head C
Keep the above steps, util it reaches the end of the linkedList.
```

**JAVA Code:**

```
public ListNode reverseOneGroup(ListNode head, ListNode nextHead) {// Reverse one k-group
ListNode prev = null;
while (head != nextHead) {
ListNode tmp = head.next;
head.next = prev;
prev = head;
head = tmp;
}
return prev;
}
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummyHead = new ListNode(0);
ListNode lastTail = dummyHead;
ListNode cur = head;
dummyHead.next = head;
while (cur != null) {
int count = 0;
while (cur != null && count < k-1) {// Find the tail of the current k-group
count++;
cur = cur.next;
}
if (cur == null) break;// Reached the end: the remaining nodes are less than k
cur = cur.next;// Next head
lastTail.next = reverseOneGroup(head, cur);// lastTail: connect with the new head after reversal
head.next = cur;// curTail: connect with the next head. (head is reversed to the current tail)
lastTail = head;
head = cur;// Set head with the next head
}
return dummyHead.next;
}
```

**Solution2. Recursive Solution - Special thanks to @shpolsky**

As only constant memory is allowed, recursive solution actually doesn't satisfy the requirement, because it needs system stack space for recursion.

```
1) Find kth node (Next head after k-group)
2) Reverser k..end-1 as the next node of 0..k-1(k-group)
3) Reverse 0..k-1(k-group)
4) Keep the above steps recursively
```

**Time Complexity: O(n)**

```
1) For each k-Group, we need O(k)(Find kth node) + O(k)(Reverse k nodes)=O(2k)=O(k)
2) There're (n / k) groups totally
So the total time complexity = O(k) * (n / k) = O(k * (n / k)) = O(n).
```

**JAVA Code:**

```
public ListNode reverseKGroup(ListNode head, int k) {
ListNode nextHead = head;
for (int i = 0; i < k; i++) { //Find the next head after k-group (kth node, because k-group is 0..k-1)
if (nextHead == null) return head;// less than k nodes left, return the orginal head
nextHead = nextHead.next;
}
ListNode previousTail = head;// head of (0..k-1)group becomes the previous tail of (k..n)group
// reverse 0..k-1
ListNode prev = null;
for (int i = 0; i < k; i++) {
ListNode next = head.next;
head.next = prev;// point head.next back to previous
prev = head;// update current 'prev'
head = next;// forward head
}
// Append result of (k..n) nodes to (0..k-1) group
previousTail.next = reverseKGroup(nextHead, k);
return prev;
}
```