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

import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        // write code here
        if(head==null){
            return true;
        }
        //1.找到链表的中间节点
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;//循环结束，slow此时就是中间节点
        }
        //2.翻转中间节点后面的部分
        ListNode cur=slow.next;
        while(cur!=null){
            ListNode CurN=cur.next;
            cur.next=slow;
            slow=cur;
            cur=CurN;
        }
        //3.head往后，slow往前，直到相遇，判断值是否相同
        while(head!=slow){
            if(head.val!=slow.val){
                return false;
            }
            //考虑偶数情况
            if(head.next==slow){
                return true;
            }
            head=head.next;
            slow=slow.next;
        }
        return true;
    }
}

思路：回文的特征便是对称的值要一样，既如此，先找到中间节点，并且反转中间节点后的节点指向，这样才能比较值是否相等，不然单向不好比。第三步，比较首尾节点的大小，相等就下一个，不等就返回false，这里也要考虑偶数的情况，因为如果是偶数个节点，其实head和slow就不会相遇，但其实真的是偶数个且对应的值都一样，就只要保证head.next ==slow就可以直接返回true即可