문제 // 자료구조 // 리스트(List) // 회문 // toJava

/**
 * [회문]
 *  주어진 연결리스트가 회문인지 검사하는 함수를 작성
 *
 * [풀이]
 *  => 리스트 내부함수로 구현하는가 ?
 *  => 양방향인가 단방향인가 ?
 *  => 전체 길이를 캐싱할 수 있는가 ?
 * */

public class Q06 {

    public static void main(String[] args) {

    }

    /* Node */
    static class Node {
        Node next;
        int data;
        Node(int data) {
            this.data = data;
        }
    }

    /* isPalindromeA */
    static boolean isPalindromeA(Node head) {
        Node reversed = reverseAndClone(head);
        return isEqual(head, reversed);
    }

    /* reverseAndClone */
    static Node reverseAndClone(Node node) {
        Node head = null;
        while(node != null) {
            Node n = new Node(node.data);
            n.next = head;
            head = n;
            node = node.next;
        }
        return head;
    }

    /* isEqual */
    static boolean isEqual(Node origin, Node reverse) {
        while(origin != null && reverse != null) {
            if(origin.data != reverse.data) {
                return false;
            }
            origin = origin.next;
            reverse = reverse.next;
        }
        return origin == null && reverse == null;
    }

    /* isPalindromeB - stack */
    static boolean isPalindromeB(Node head) {
        Stack<Integer> stack = new Stack();
        Node fast = head;
        Node slow = head;
        boolean isMiddle = false;

        while(slow.next != null) {
            if(!isMiddle)
                stack.push(slow.data);
            else
                if(stack.pop() != slow.data) return false;
            slow = slow.next; // == 한칸씩이동 ==
            if(fast.next == null) {
                isMiddle = true;
                stack.pop();
            } else {
                if(fast.next.next == null) {
                    isMiddle = true;
                } else {
                    fast = fast.next.next; // == 두칸씩이동 ==
                }
            }
        }
        return true;
    }
}