题解 | #判断一个链表是否为回文结构，时间O(n)，空间O(1)#

import java.util.*;

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

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    //时间O(n) 空间O(1)
    public boolean isPail (ListNode head) {
        if(head == null) return false ;
        //只有一个节点
        if(head.next == null) return true ;
        //只有两个节点
        if(head.next.next == null) {
            if(head.val == head.next.val) {
                return true ;
            } else {
                return false ;
            }
        }
        //三个及以上的节点(使用快慢指针，找到中点，将中点以后的链表翻转，
        //然后依次迭代两条链表，判断回文
        ListNode fast = head ;
        ListNode slow = head ;
        while(!(fast.next == null || fast.next.next == null)) {
            fast = fast.next.next ;
            slow = slow.next ;
        }
        //此时slow指向中点，将中点以后的链表翻转
        ListNode left = head ;//左部分
        ListNode tmp = slow.next ;
        slow.next = null ;
        ListNode right = reverse(tmp) ;//右部分
        //开始判断回文
        while(left != null && right != null) {
            if(left.val != right.val) {
                return false ;
            }
            left = left.next ;
            right = right.next ;
        }
        return true ;       
    }
    public ListNode reverse(ListNode list) {
        ListNode pre = null ;
        ListNode cur = list ;
        ListNode nxt = null ;
        while(cur != null) {
            nxt = cur.next ;
            cur.next = pre ;
            pre = cur ;
            cur = nxt ;
        }
        return pre ;
    }
}