题解 | 链表的回文结构

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
        ListNode f=A,s=A;
        while(f!=null&&f.next!=null){
            s=s.next;
            f=f.next.next;
        }
        //f是中间节点。（若为偶数，则为中间节点的下一个节点）
        ListNode pre=s,cur=s.next,nex=cur;
        while(cur!=null){
            nex=cur.next;
            cur.next=pre;
            pre=cur;
            cur=nex;
        }
        //pre是反转后的链表的头节点
        s.next=null;
        ListNode p1=A,p2=pre;
        while(p1!=null&&p2!=null){
            if(p1.val!=p2.val){
                return false;
            }
            p1=p1.next;
            p2=p2.next;
        }
        return true;
    }
}