package com.jiucaiyuan.net.algrithm.linked;



import java.util.Stack;



/**

 * 【问题】给定一个单项链表的头结点head，请判断该链表是否是回文结构

 * 【例子】

 * 1——>2——>1，返回true

 * 1——>2——>2——>1，返回true

 * 15——>6——>15，返回true

 * 1——>2——>3，返回false

 * 【要求】时间复杂度O(N)，空间复杂度O(1)

 * 【思路】快慢指针，快指针走到末尾，慢指针走到终点，终点之后遍历时，同时后半段给逆序，然后再遍历前半部分和后半部分，看是否一样

 *

 * @Author jiucaiyuan  2022/4/4 22:58

 * @mail services@jiucaiyuan.net

 */



public class IsPalindrome {

    /**

     * 使用额外n空间 栈

     *

     * @param head

     * @return

     */

    public static boolean isPalindrome(ListNode head) {

        print(head);

        Stack<ListNode> stack = new Stack<>();

        ListNode curr = head;

        while (curr != null) {

            stack.push(curr);

            curr = curr.next;

        }



        while (head != null) {

            if (head.val != stack.pop().val) {

                return false;

            }

            head = head.next;

        }

        return true;

    }



    /**

     * 使用n/2的额外空间 栈

     *

     * @param head

     * @return

     */

    public static boolean isPalindrome2(ListNode head) {

        print(head);

        if (head == null || head.next == null) {

            return true;

        }

        ListNode right = head.next;

        ListNode curr = head;

        while (curr.next != null && curr.next.next != null) {

            right = right.next;

            curr = curr.next.next;

        }

        Stack<ListNode> stack = new Stack<>();

        while (right != null) {

            stack.push(right);

            right = right.next;

        }

        while (!stack.isEmpty()) {

            if (head.val != stack.pop().val) {

                return false;

            }

            head = head.next;

        }

        return true;

    }



    /**

     * 使用O(1)的额外空间

     *

     * @param head

     * @return

     */

    public static boolean isPalindrome3(ListNode head) {

        print(head);

        if (head == null || head.next == null) {

            return true;

        }



        ListNode n1 = head;

        ListNode n2 = head;

        while (n2.next != null && n2.next.next != null) {  //find mid node

            n1 = n1.next;  //n1 to mid

            n2 = n2.next.next;  //n2 to end

        }



        //n1 开始逆序

        n2 = n1.next;   //n2 ——> right part first node

        n1.next = null;  //mid next ——> null

        ListNode n3 = null;

        while (n2 != null) {

            n3 = n2.next;   //n3——>save next node

            n2.next = n1;   //node of right to convert

            n1 = n2;

            n2 = n3;

        }



        //n1 和 n2 从两个链表的头开始处理，检查是否相同

        n3 = n1;  //n3 ——> save last node

        n2 = head; //n2——> left first node

        boolean res = true;

        while (n1 != null && n2 != null) {  // check palindrome

            if (n1.val != n2.val) {

                res = false;

                break;

            }

            n1 = n1.next;  //left to mid

            n2 = n2.next;  //right to mid

        }



        //恢复右半部分

        n1 = n3.next;

        n3.next = null;

        while (n1 != null) {  //recover list

            n2 = n1.next;

            n1.next = n3;

            n3 = n1;

            n1 = n2;

        }

        return res;

    }



    public static void main(String[] args) {

        ListNode head = new ListNode(0);

        ListNode node1 = new ListNode(1);

        ListNode node2 = new ListNode(2);

        ListNode node3 = new ListNode(1);

        ListNode node4 = new ListNode(0);

        head.next = node1;

        node1.next = node2;

        node2.next = node3;

        node3.next = node4;



        System.out.println(isPalindrome(head) + " vs " + isPalindrome2(head) + " vs " + isPalindrome3(head));



        ListNode head2 = new ListNode(0);

        ListNode node12 = new ListNode(1);

        ListNode node22 = new ListNode(1);

        ListNode node32 = new ListNode(0);

        head2.next = node12;

        node12.next = node22;

        node22.next = node32;



        System.out.println(isPalindrome(head2) + " vs " + isPalindrome2(head2) + " vs " + isPalindrome3(head2));



        ListNode head02 = new ListNode(0);

        ListNode node012 = new ListNode(1);

        ListNode node022 = new ListNode(2);

        ListNode node032 = new ListNode(0);

        head02.next = node012;

        node012.next = node022;

        node022.next = node032;

        System.out.println(isPalindrome(head02) + " vs " + isPalindrome2(head02) + " vs " + isPalindrome3(head02));

    }



    public static void print(ListNode head) {

        ListNode curr = head;

        while (curr != null) {

            System.out.print("\t" + curr.val);

            curr = curr.next;

        }

        System.out.println();

    }

}