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

import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    /**
    逆转链表,不会推荐去练一下
     */
    private ListNode reverseList(ListNode head) {
        ListNode cur = null;
        ListNode node = null;
        while(head!=null) {
            cur = head.next;
            head.next = node;
            node = head;
            head = cur;
        }
        return node;
    }

    public boolean chkPalindrome(ListNode A) {
        if(A==null) {
            return false;
        }
        // write code here
        /**
        此处fast = A.next 使得原本寻找中间节点的操作改变，返回链表的中间结点。如果有两个中间结点，则返回第一个中间结点
        原本fast = A 时返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
         */
        ListNode fast = A.next;
        ListNode slow = A;
        while(fast!=null&&fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        /**
        通过逆转中间节点之后的链表，让一个指针从头开始，另一个从中间开始，如果有不相等就不为回文结构
         */
        slow.next = reverseList(slow.next);
        ListNode a1 = A;
        ListNode a2 = slow.next;
        while(a2!=null) {
            if(a2.val!=a1.val) {
                return false;
            }
            a2=a2.next;
            a1=a1.next;
        }
        return true;
    }
}