链表--回文字符串

字符串通过链表存储

a->b->c->b->a
使用双指针形式，慢指针向后走一步，快指针向后走两步。当快指针走到尾结点时，慢指针走到终点。逆序比较

    public static void main(String[] args) {
        LinkedNode linkedNode5 = new LinkedNode("a");

        LinkedNode linkedNode4 = new LinkedNode("b",linkedNode5);

        LinkedNode linkedNode3 = new LinkedNode("c",linkedNode4);

        LinkedNode linkedNode2 = new LinkedNode("c",linkedNode3);

        LinkedNode linkedNode1 = new LinkedNode("b",linkedNode2);

        LinkedNode linkedNode0= new LinkedNode("a",linkedNode1);

        System.out.println(isPalindrome(linkedNode0));

    }


    public static Boolean isPalindrome(LinkedNode node) {

        //如果只有一个节点有数据，必然是真的
        if (node == null || node.next == null) {
            return true;
        }

        //尽快走到链尾
        LinkedNode p = node;

        //寻找中间结点
        LinkedNode q = node;

        //p或者p.next为空时，此时q正是中间结点。
        LinkedNode prev = null;
        LinkedNode temp ;
        while (p != null && p.next != null) {

            //p节点向后两步
            p = p.next.next;

            //q节点逆序
            temp = q.next;
            q.next = prev;
            prev = q;


            //q节点向后一步
            q = temp;

        }

        //奇数，此时q节点在中间结点。q的下一结点，与prev比较。偶数，q为中间偏右结点。q和prev比较
        if (p !=null){
            q=q.next;
        }

        while (q !=null && prev !=null){
            if(!q.item.equals(prev.item)){
                return false;
            }

            q= q.next;
            prev = prev.next;
        }

        return true;
    }

    private static class LinkedNode {

        private String item;

        private LinkedNode next;

        public LinkedNode(String item) {
            this.item = item;
        }

        public LinkedNode(String item, LinkedNode next) {
            this.item = item;
            this.next = next;
        }
    }