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

1.思路

• 1.先通过快慢指针，找到中间结点
• 2.对中间结点后面的链表进行反转
• 3.指针从两端开始移动，如果符合回文结构，在奇数情况下相与，在偶数情况下相邻

2.图解

3.解题步骤

• 1.判断头结点是否为空，判断是否只有一个结点
• 2.设立快慢指针，找到中间的结点
• 3.设cur结点为中间结点的下一个结点,进行后面链表的反转
• 4.当cur为空时，说明slow到了末尾
• 5.让头结点和slow向中间移动
• 6.如果两端的值不等时，直接返回false
• 7.在奇数个结点的情况下，head和slow相遇
• 8.在偶数结点的情况下，head的下一个结点就是slow

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if (A == null) {
            return false;
        }
        if (A.next == null) {
            return true;
        }
        ListNode fast = A;
        ListNode slow = A;
        //寻找中间结点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //翻转
        ListNode cur = slow.next;//cur代表当前需要翻转的结点
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //一个从前往后，一个从后往前，进行比较， 直到slow和head相遇
        while (slow != A) {
            if (slow.val != A.val) {
                return false;
            }
            if (A.next == slow) { //走到这里两个val值一样，偶数情况
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
    }
}