[数据结构与算法]链表的回文结构（采用翻转后半段链表，然后从两头开始比较的思想）

• 链表的回文结构：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构

public boolean chkPalindrome(ListNode A) {
        //链表为空，不是回文结构
        if(A == null){
            return false;
        }
        //只有一个结点，为回文结构
        if(A != null && A.next == null){
            return true;
        }
        //1.找中间结点：把链表分成两部分
    	ListNode fast = A;
    	ListNode slow = A;
    	while(fast!=null && fast.next!=null){
    		fast = fast.next.next;
    		slow = slow.next;  
    		//此时，slow为中间结点，即后一段的开始结点
    	}
    	//2.翻转后面一部分链表（头插法）
    	ListNode prev = slow;
    	ListNode cur = slow.next;
    	while(cur != null){
            ListNode curnext = cur.next;
    		cur.next = prev;
    		prev = cur;
    		cur = curnext;
    	}
    	//3.从两头向中间比较
    	ListNode q = prev;
    	while(A != slow){
    		if(A.val != q.val){
    			return false;
    		}
            else{
                if(A.next == q){  //链表有偶数个结点
                    return true;
                }
    		    A = A.next;
    		    q = q.next;
            }
    	}
    	return true;
    }