```
// In each recursion, finding k nodes takes O(k) time; node reverse time is O(k), thus each recursion takes O(2k) time.
// The recursion depth is n/k
// Thus the total time is O(n)
// Space cost is O(1)
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || head.next == null || k == 0 ) return head;
ListNode start = head, end = head;
int counter = 1;
// Count k nodes
while (end.next != null && counter < k) {
end = end.next;
counter++;
}
if (counter == k) { // If there exists k nodes, reverse them.
ListNode next = end.next; // Record the (k+1) th node
reverser(start, end); // Time O(k)
start.next = reverseKGroup(next, k); // start is now pointing to the tail of the reversed list. Recursion depth is n/k
return end;
}
else { // If there are less than k nodes, then return.
return start;
}
}
// Reverse list (Time complexity O(k))
private void reverser(ListNode start, ListNode end) {
ListNode previous = null;
while (start != end) {
ListNode next = start.next;
start.next = previous;
previous = start;
start = next;
}
start.next = previous;
}
}
```