牛客OR36—链表的回文结构(较难题 思路+代码)

链表的回文结构

思路：题要求判断一个链表是否为回文链表
大概做法：找出中间节点，从中间位置分割成AB两个链表，让B链表逆序，然后AB链表同时遍历val值，不相等就不是回文链表

具体：1.先找出链表的中间节点(使用快慢指针) 注意考虑 偶数节点，奇数节点时，中间节点的取值
原因:①偶节点的中间节点在slow的前一个节点，因为链表有4个节点的时候slow在第三个节点的位置，我们让prev指向slow的前一个，这时分割AB链表的时候，AB链表节点相等，可以判断val值;②奇节点的中间位置就是slow，因为链表有3个节点的时候，slow就在第二个节点上，我们分割AB链表，逆序B链表，不用判断中间节点，只用判断两头的节点是否一样，因为1-》2-》1 就是一个回文链表，链表中的2值不用判断
2.分割链表 分割出AB两个链表
3.逆序链表
4.判断AB链表的两个val值
5.判断完后，将B链表再次逆序然后连接两个链表

public class PalindromeList {
    public ListNode GetMiddleList(ListNode A){
        ListNode fast = A;
        ListNode slow = A;
        ListNode prev = null;
        while(null != fast && null != fast.next){
            fast = fast.next.next;
            prev = slow;//保存slow的上一个节点 
            slow = slow.next;
        }
        if(fast == null){
            return prev;//偶数个节点的时候 返回slow的前一个 
        }
        //奇数个节点的时候 中间节点不用判断
        return slow;
    }
    
    public ListNode ReverseList(ListNode A){
        ListNode cur = A;
        ListNode next = null;
        ListNode prev = null;
        while(null != cur){
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    
    public boolean chkPalindrome(ListNode A) {
      ListNode mid = GetMiddleList(A);//获取中间节点
        ListNode B = mid.next;
        mid.next = null;//形成两个节点
        //逆序B链表
        B = ReverseList(B);
        ListNode curA = A;
        ListNode curB = B;
        boolean tmp = true;
        //AB链表遍历val值
        while(null != curB){
            if(curA.val != curB.val){
                tmp = false;
                break;
            }
            curA = curA.next;
            curB = curB.next;
        }
        //逆序链表 连接链表
        B = ReverseList(B);
        mid.next = B;
        return tmp;
    }
}