单链表回文判断

public boolean isPalindromeByArray(Node node){
        if (node == null) return false;
        Node fast = node;
        Node slow = node;
        if (node.next == null) return true;

        /**
         * 找到中间结点，同时用数组逆插左侧元素并保存。
         *  nodeList.add(0, slow.data); 在指定位置插入元素，原位置及之后的依次向右移动一位。
         */
        List<Integer> nodeList = new ArrayList<Integer>();
        nodeList.add(0, slow.data);
        while (fast.next != null && fast.next.next != null ) {

            fast = fast.next.next;
            slow = slow.next;
            nodeList.add(0, slow.data);
        }


        if (fast.next != null){
            // fast.next不为空，数据为偶数。
            slow = slow.next;
        }
        Node curr = slow;
        int i = 0;
        while (null != curr){
            if (curr.data != nodeList.get(i)){
                return false;
            }
            curr = curr.next;
            i++;
        }
        return true;
    }

/**
     * 基于栈比较是否为回文--半栈
     * @param node
     * @return
     */
    public boolean isPalindromeByStack(Node node){
        if (node == null) return false;
        Node fast = node;
        Node slow = node;
        if (node.next == null) return true;

        /**
         * 找到中间结点，同时用栈保存左侧数据。
         *  
         */
        Stack<Integer> nodeList = new Stack<Integer>();
        nodeList.push(slow.data); // 1 2 3
        while (fast.next != null && fast.next.next != null ) {

            fast = fast.next.next;
            slow = slow.next;
            nodeList.push(slow.data); // 1 2 3
        }


        if (fast.next != null){
            // fast.next不为空，数据为偶数。
            slow = slow.next;
        }
        Node curr = slow;
        int i = 0;
        while (null != curr){
            if (curr.data != nodeList.pop()){
                return false;
            }
            curr = curr.next;
            i++;
        }
        return true;
    }

    /**
     * 不含逻辑头节点的回文链表判断
     * 思路：
     * 遍历一遍链表,得到链表长度n,根据长度的奇偶,找到中间节点,将左半边的链表反转,然后从中间节点分两个方向向左右两边遍历,是否是回文;
     * 
     * 对左半部分链表进行反转,还原为最初的链表（目前函数未实现左半部分链表还原）
     * 
     * 
     * 1 2 3 4 5 8 9 slow 4 fast 9
     * 1 2 3 4 5 8  slow  3 fast 5
     * @return
     */
    public  boolean isPalindrome(Node head){
        if (head == null) return false;
        PrintUtill.println("开始执行找到中间节点");
        Node fast = head;
        Node slow = head;
        if (fast.next == null){
            System.out.println("只有一个元素");
            return true;
        }
        /**
         * 快的一次走两步,慢的一次走一步那么最后快的结束了慢的走了一半
         */
        while (fast.next !=null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        Node leftLink = null;
        Node rightLink = null;
        /**
         * 获取中间结点左右两部分，反转左侧部分。
         * fast.next == null ：节点数目为奇数,且slow一定为为中间节点
         * fast.next.next  == null ：节点数目为偶数，slow、slow.next 均为中心结点
         */
        rightLink = slow.next;
        if (fast.next  == null){
            leftLink = inverseLinkListToEnd(slow).next;
        }else {
            leftLink = inverseLinkListToEnd(slow);
        }
        /**
         * 从此处开始同步向两边比较
         */
        return TFResult(leftLink, rightLink);
    }
    /**
     * 比较是否为回文
     * @param left
     * @param right
     * @return
     */
    public boolean TFResult(Node left, Node right){

        while (left != null && right != null){
            if (left.data != right.data){
                return false;
            }
            left = left.next;
            right = right.next;
        }

        return true;
    }


    /**
     * 反转中间结点的左半部分，返回以end结点为头节点的链表。
     * @param end
     * @return
     */
    public Node inverseLinkListToEnd(Node end) {
        Node pre = null;
        Node cur = head;
        Node next = null;

        /**
         * 反转中间结点之前的结点
         */
        while (cur!=end){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        cur.next = pre;
        return cur;
    }