Java Recursion Solution - Easy to understand (8 ms)

• ``````// 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) {

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;
}
}
``````

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