# Short but recursive Java code with comments

• Hi, guys!
Despite the fact that the approach is recursive, the code is less than 20 lines. :)

``````public ListNode reverseKGroup(ListNode head, int k) {
ListNode curr = head;
int count = 0;
while (curr != null && count != k) { // find the k+1 node
curr = curr.next;
count++;
}
if (count == k) { // if k+1 node is found
curr = reverseKGroup(curr, k); // reverse list with k+1 node as head
// head - head-pointer to direct part,
// curr - head-pointer to reversed part;
while (count-- > 0) { // reverse current k-group:
ListNode tmp = head.next; // tmp - next head in direct part
head.next = curr; // preappending "direct" head to the reversed list
curr = head; // move head of reversed part to a new node
head = tmp; // move "direct" head to the next node in direct part
}
}
}
``````

Hope it helps!

• Very concise solution. Thank you for sharing!

• Although it may not meet the requirement of the question that that it should use constant memory, the code is really nice and concise.

• sweet code and it's easy to understand. Thanks!

• Actually, there is a way to write recursive in O(1) space. Just put `reverseKGroup(curr, k);` at the end.

• I don't quite understand. How can a recursive function only use O(1) space? In my opinion, a recursive function must occupy at least O(n) stack space, where n is the depth of the recursion.

• Consider this structure

``````recursive(x){
if(x<1)
return 0
else
recursive(x-1)
}``````

• Could you please give more detail on the space complexity? I think even the function is void type, we still need O(k) space on stack for storing the parameters in each recursion.

• You are right. I found out that the stack is always needed. There must be O(k) space required.

• this is so elegant..

• so beautiful...

• what you said is the tail call recursion. I think java can optimize tail call recursion to O(1). since it will be nothing more than a while loop. But, it will become a totally different solution, not just put the recursive call to the end

• It's simply WRONG if put reverseKGroup(curr, k); at the end.

• this is cray..

• The problem only allowed O(1) memory,
while your solution uses O(N) space.

• Great solution. Really easy to understand with comments.

• this is beautiful, easy to understand

• Check this out. 16 Lines Non-recursive.

``````public ListNode reverseKGroup(ListNode head, int k) {
int n = 0;
for (ListNode i = head; i != null; n++, i = i.next);

ListNode dmy = new ListNode(0);
for(ListNode prev = dmy, tail = head; n >= k; n -= k) {
for (int i = 1; i < k; i++) {
ListNode next = tail.next.next;
tail.next.next = prev.next;
prev.next = tail.next;
tail.next = next;
}

prev = tail;
tail = tail.next;
}
return dmy.next;
}``````

• What would be the time complexity ?

• What would be Time Complexity ?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.