题解 | #判断一个链表是否为回文结构#

对链表遍历以及其特性的研究，可以考虑使用快慢指针的思想

（1）使用快慢指针,快指针一次走两步，慢指针走一步，同时完成链表的反转工作，直到快指针走到链表尾；

（2）此时，链表的前半部分都已经反转过来，再根据链表节点的奇偶特点（考虑回文结构），变换指针位置为反转部分的头节点和原链表中间节点；

（3）顺序遍历两个指针，比较节点值

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

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        //使用快慢指针,慢指针反转链表
        ListNode fast = head, slow = head;
        ListNode node = null;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            ListNode tmp = slow.next;
            slow.next = node;
            node = slow;
            slow = tmp;
        }
        //变换指针位置（根据链表节点的奇偶）
        fast = fast == null ? slow : slow.next;
        slow = node;
        //从中间和前段反转部分头节点开始比较值
        while(fast != null){
            if(fast.val != slow.val)    return false;
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
}

时间复杂度O(n)，空间复杂度O(1)