题解 | #链表的回文结构#

链表的回文结构是一道经典的题目，曾经作为字节跳动的面试题，值得大家熟练掌握。

对于数组的回文结构判断，我们只需要设置两个变量，一个从0下标开始，另一个从length-1下表开始，分别从下标递增的方向以及下标递减的方向遍历数组，进而判断数组是否为回文结构。

借助数组回文结构的判断思想，我们可以运用到链表当中，但是对于单链表，我们无法从尾节点开始遍历数组，由此，如何找到中间节点，并将链表反转就成了一个难题，我们可以采用如下方法：

首先利用双指针的思想，通过一遍的遍历，就可以得到链表的中间节点（涉及到链表中间节点的找法，也是一道经典题目）；然后把中间及以后的节点进行反转，这样就可以从两个方向遍历整个链表，以此来判断该链表是否为回文结构。

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        if (A == null) {
            return false;
        }
        if (A.next == null) {
            return true;
        }
        // 找到链表中间节点
        ListNode fastNode = A;
        ListNode slowNode = A;
        while (fastNode != null && fastNode.next != null) {
            fastNode = fastNode.next.next;
            slowNode = slowNode.next;
        }
        // 反转中间节点及以后的链表
        ListNode cur = slowNode.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slowNode;
            slowNode = cur;
            cur = curNext;
        }
        // 判断是否为回文
        ListNode headNodeA = A;
        ListNode headNodeB = slowNode;
        while (headNodeA != headNodeB) {
            if (headNodeA.val != headNodeB.val) {
                return false;
            }
            // 节点为偶数的特殊情况的解决
            if (headNodeA.next == headNodeB) {
                return true;
            }
            headNodeA = headNodeA.next;
            headNodeB = headNodeB.next;
        }
        return true;
    }
}