package list;

/**
 * @ClassName PalindromeLink
 * @Description 单链表形式验证输入是否为回文
 * @Author lixin
 * @Date 2020/5/18 10:47 上午
 */
public class PalindromeLink {

    /**
     * 输入链表是否为回文
     * 思路 ：
     * 1、通过"快慢指针"方式 ，创建2个指针，快指针每次向下走2步，慢指针每次向下走1步，当快指针到最后一个节点时，慢指针指向的即为中间节点
     * 2、慢指针每次向后迁移一个节点后，反转走过的节点。
     * 3、找到中间指针后，创建一个新指针，指向中间节点，然后慢指针继续向下单次移动一个节点，新指针向下单次移动一个节点，对比两个节点内容，如果不相等，则不是回文 ，全部相等则为回文。
     * 4、注意链表奇偶数区别
     * @param head
     * @return
     */
    public boolean isPalindrome(Node head){

        Node fast = head;
        Node slow = head;
        Node next = slow.next;

        while(true){
            if(null == fast || null == fast.next || null == fast.next.next){
                break;
            }

            /**
             * 快指针向下走2步，这里要先移动快指针，否则慢指针批转后，会影响快指针移动
             */
            fast = fast.next.next;

            /**
             * 慢指针向下走1步，并反转经过的节点
             * 要点：
             * 1、需要记录3个指针：当前指针、上一节点、下一节点
             * 2、当前指针向后移动
             * 3、反转指向关系
             */
            Node pre = slow; //记录上一节点
            slow = next; //当前指针向后移动
            next = slow.next; //记录下一节点
            pre.next = null; //删除上一节点的next
            slow.next = pre; //反转
        }

        /**
         * 如果链表长度奇偶与快指针结束关系
         * 长度奇数：fast.next == null
         * 长度偶数：fast.next != null
         *
         * 当链表长度为奇数时，跳过中间节点，从反转后的第一个节点开始比较
         */
        if(null == fast.next){
            slow = slow.next;
        }

        boolean palindrome = true;
        while(true){
            if(null == slow || null == next){
                break;
            }

            if(slow.data != next.data){
                palindrome = false;
                break;
            }

            slow = slow.next;
            next = next.next;
        }

        return palindrome;
    }

    public static void main(String[] args) {
        ListOperator operator = new ListOperator();
        /**
         * 数组转链表，可自行实现
         */
        Node head = operator.fromArray(new Integer[]{1,2,3,3,2,1});

        PalindromeLink link = new PalindromeLink();
        System.out.println(link.isPalindrome(head));
    }
}