CTCI 2.7

Implement a function to check if a linked list is a palindrome.

CTCI 2.7-1.java

//iterative
public static boolean checkPalindrome(Node root){
    Node slow = root;
    Node fast = root;
    Stack<Integer> previousNode = new Stack<>();
    while(fast != null && fast.next != null){
        previousNode.push(slow.value);
        slow = slow.next;
        fast = fast.next.next;
    }
    
    if(fast != null) slow = slow.next;
    
    while(slow != null){
        if(slow.value != previousNode.pop()) return false;
        slow = slow.next;
    }
    
    return ture;
}

CTCI 2.7-2.java

//recursive
public static Result checkPalindrome(Node root, int count){
    if(root == null || count == 0) return Result(null, false);
    else if(count == 1) return Result(root.next, true);
    else if(count == 2) return Result(root.next.next, root.value == root.next.value);
    
    Result before = checkPalindrome(root.next, count -2);
    if(!before.byfar) return Result;
    else{
        Node nextRunner = before.runner.next;
        return Result(nextRunner, root.value == before.runner.value)
    }
}

class Result{
    Node runner;
    boolean byFar;
    Result(Node r, boolean b){
        this.runner = r;
        this.byfar = b;
    }
}