如果字符串是通过 单链表 来存储的，那该如何来判断是一个回文串呢？

1. 通过快慢指针定位中间节点
2. 从中间节点对后半部分逆序
3. 前后半部分比较，判断是否为回文
4. 后半部分逆序复原

Github代码地址

一、通过快慢指针定位中间节点

什么是快慢指针？
两个表示节点变量，在循环中变量a每次走一步，变量b每次走两步，则变量b称为快指针，变量a称为慢指针。（快慢指针走的差值可以为非0的任意正数）

数据准备：java 提供的链表 LinkedList 是一个双向链表，单链表需要我们自己实现。
创建类 Node：

/**
 * 元素结点
 *
 * @author : zyf
 * @since : 2018-12-26 17:43
 **/
public class Node {
    private int value;
    private Node next;

    public Node(int value) {
        this.value = value;
    }

    public Node() {
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

在测试类中，准备好链表数据：

    public static Node prepData(){
        //拼接链表：
        Node headNode = new Node(0);
        Node current = headNode;
        int[] a = {1,2,3,4,4,3,2,1,0};
        for (int i = 0; i < 9; i++) {
            Node temp = new Node(a[I]);
            current.setNext(temp);
            current = temp;
        }
        return headNode;
    }

通过快慢指针获取该链表的中间节点：

    public static Node getMiddleNode(Node headNode){
        Node lowlyNode = headNode.getNext();
        Node fastNode = null;
        if(lowlyNode != null){
            fastNode = lowlyNode.getNext();
        }
        while (fastNode != null){
            if(fastNode.getNext() == null){
                //说明链表长度为奇数
                //说明此时lowlyNode为中间结点
                return lowlyNode;
            }

            if(fastNode.getNext().getNext() == null){
                //说明链表长度为偶数
                //此时应该根据规定（看你的需求）来返回上中结点还是下中结点
                //假设链表长度为4（0，1，2，3）
                //上中结点就是1，下中结点就是2
                //此处我返回下中结点
                return lowlyNode.getNext();
            }
            //每次循环，快指针前进两步
            fastNode = fastNode.getNext();
            fastNode = fastNode.getNext();
            //每次循环，慢指针前进一步
            lowlyNode = lowlyNode.getNext();
        }

        return lowlyNode;
    }

二、从中间节点对后半部分逆序

如何根据一个给定的头结点对该单链表进行逆序？
思路如下：

image

对单链表逆序的代码如下：

public static Node reverseNode(Node head){
    Node temp = head.getNext();
    Node flag = temp.getNext();

    head.setNext(null);

    while (flag != null){
        temp.setNext(head);

        //temp 变成了头
        head = temp;
        //flag 变成了 temp
        temp = flag;

        flag = flag.getNext();
    }

    temp.setNext(head);
    return temp;
}

所以若想在中间结点后开始逆序：

• 若链表长度为奇数，则在中间结点的 next 结点开始逆序
• 若链表长度为偶数，则在下中结点开始逆序

三、前后半数据比较，判断是否回文

    /**
     * @param head  头结点
     * @param middleHead <p>若链表长度为奇数，则在中间结点的 next 结点开始逆序，
     *                   若链表长度为偶数，则在下中结点开始逆序<p/>
     * @return
     */
    public static boolean isPalindrome(Node head,Node middleHead){

        /**
         * middleHead肯定是在head后面的
         * 也就是 middleHead 会先走到结尾，所以此处用 middleHead 来判断
         */
        while (middleHead != null){
            if(head.getValue() != middleHead.getValue()){
                return false;
            }
            
            head = head.getNext();
            middleHead = middleHead.getNext();
        }

        return true;
    }

四、后半部分逆序复原

与第 二 部分一样，再执行一遍 reverse() 即可。

五、测试

    public static void main(String[] args) {

        //准备数据
        Node headNode = prepData();
        //获取中结点
        Node middleNode = getMiddleNode(headNode);
        //将后半段逆序
        Node reverseNode = reverseNode(middleNode);
        //判断是否为回文
        boolean palindrome = isPalindrome(headNode, reverseNode);
        //逆序复原
        middleNode = reverseNode(reverseNode);
        System.out.println(palindrome);

    }