# Java recursive optimistic approach: undo the last few reversals if we didn't find k items

• The idea to this solution is that we continue to reverse the list node by node until either we find that we successfully reverted k items and so we commit that reversal or we find that the list ended before finding k items at which point we recursively undo those reversals.

``````public class Solution {

/**
* Wrapper class to be able to return two values
**/
public class Result {
boolean commit; // Will tell wether we found k items in the process that we can commit to reverse or not
public Result(boolean commit, ListNode head) {
this.commit = commit;
}
}

/**
* @current: last node to which we've reversed its pointer
* @next: node that we will be reversing its pointer
* @lastTail: tail of the currently being reverted k-set of items, once we've gone through all k items we'll link that tail to the head of the next k-set
* @k: k as per it's definition
* @count: how many items from the k-set we have reverted so far
**/
Result reverse(ListNode current, ListNode next, ListNode lastTail, int k, int count) {
if ( k <= 1 ) {
// Edge case, return the same list
return new Result(true, next);
} else if ( next == null ) {
// We've reached the end, all that's left is to determine if we can commit to the reversal or undo it
return new Result(count == 0, count == 0 ? null : current);
}

// Reverse the pointers
ListNode aux = next.next;
next.next = current;
Result result;

if ( count < k-1 ) {
// We haven't reached the end of a k-set of items, do the rest and then we'll decide
result = reverse(next, aux, lastTail, k, count+1);

if ( result.commit ) {
// We can commit to the reversal because there were k items to reverse
return result;
} else {
// Undo the reversal, our optimistic approach didn't pay off
next.next = aux;
return new Result(false, next);
}
} else {
// We've reached the end of a k-set of items, make sure to link the tail of the reversed list to the next list
result = reverse(next, aux, aux, k, 0);