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


  • 0
    A

    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
            ListNode head; // The new head of the list
            public Result(boolean commit, ListNode head) {
                this.commit = commit;
                this.head = head;
            }
        }
        
        /**  
         * @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);
                lastTail.next = result.head;
                
                return new Result(true, next);
            }
        }
        
        public ListNode reverseKGroup(ListNode head, int k) {
            return reverse(null, head, head, k, 0).head;
        }
    }
    

Log in to reply
 

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