package string.string1_5;

public class Palindrome

{

    /**

     * 从两头向中间移动

     * @param str

     * @return

     */

    public static boolean isPalindrome(String str)

    {

        if(str == null || str.equals(""))

            return false ;

        int left = 0 ;

        int right = str.length()-1 ;

        while (left < right)

        {

            if(str.charAt(left++) != str.charAt(right--))

                return false ;

        }

        return true ;

    }

    /**

     * 从中间向两头移动

     * @param str

     * @return

     */

    public static boolean isPalindrome2(String str)

    {

        if(str == null || str.equals(""))

            return false ;

        int left = str.length()/2 ;

        int right = str.length()-1-left ;

        while (left >= 0)

        {

            if(str.charAt(left--) != str.charAt(right++))

                return false ;

        }

        return true ;

    }

    /**

     * 判断链表是否为回文

     * @param node

     * @return

     */

    public static boolean isPalindrome3(ListNode node)

    {

        //当链表为空或者链表只包含一个元素

        if(node == null || node.next == null)

            return true ;

        ListNode head = new ListNode() ;

        head.next = node ;

        ListNode slow = head ;

        ListNode quick = head ;

        while (quick.next != null)

        {

            slow = slow.next ;

            for(int i=0 ; i<2 ; i++)

                if(quick.next != null)

                    quick = quick.next ;

                else

                    break ;

        }

        ListNode f = slow.next ;

        slow.next = null ;

        ListNode l = null ;

        ListNode t = null ;

        while (f != null)

        {

            t = f ;

            f = f.next ;

            t.next = l ;

            l = t ;

        }

        slow.next = t ;

        quick = slow.next ;

        slow = node ;

        while (quick != null)

        {

            if(slow.ch != quick.ch)

                return false ;

            slow = slow.next ;

            quick = quick.next ;

        }

        return true ;

    }

    public static void main(String[] args)

    {

/*

        ListNode node1 = new ListNode('a') ;

        ListNode node2 = new ListNode('b') ;

        ListNode node3 = new ListNode('c') ;

        ListNode node4 = new ListNode('c') ;

        ListNode node5 = new ListNode('b') ;

        ListNode node6 = new ListNode('a') ;

        node1.next = node2 ;

        node2.next = node3 ;

        node3.next = node4 ;

        node4.next = node5 ;

        node5.next = node6 ;*/

        ListNode node1 = new ListNode('a') ;

        ListNode node2 = new ListNode('b') ;

        ListNode node3 = new ListNode('c') ;

        ListNode node5 = new ListNode('a') ;

        ListNode node6 = new ListNode('a') ;

        node1.next = node2 ;

        node2.next = node3 ;

        node3.next = node5 ;

        node5.next = node6 ;

        System.out.println(isPalindrome3(node1));

    }

}

class ListNode

{

    char ch ;

    ListNode next ;

    public ListNode() {}

    public ListNode(char ch) {

        this.ch = ch;

    }

}