1. 题目描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
输入：1->2->2->1
输出：true
2. 思路
- 判断链表是否为空，如果为空，那么链表就是回文的
- 找到中间元素
- 定义两个指针
slow和fast，fast每次移动两步，slow每次移动一步，当fast走到链表中的最后一个节点是，slow就指向了链表的中间节点。
反转链表后半部分的元素
- 定义指针
cur指向中间节点的next - 从中间节点循环遍历链表
- 定义指针
curNext指向cur的next（保存下一个节点） - 将当前节点的
next指向slow slow移动到当前节点的cur位置cur移动到下一个节点
同时遍历反转后的链表和原始链表的前半部分，并比较每个节点的值。如果所有的节点都匹配，那么链表就是回文；否则它不是回文。
- 一个从前一个从后循环遍历链表，直到相遇
- 判断两个当前节点是否相同，如果不同返回
false - 如果相同判断
head的next等不等于slow，如果等于直接返回true（链表节点个数为偶数个） head移动到下一个节点slow移动到下一个节点
3. 代码
import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class PalindromeList { public boolean chkPalindrome(ListNode head) { if (head == null) { return true; } // write code here // 1.找到中间元素 ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } // 2.反转链表 ListNode cur = slow.next; while (cur != null) { ListNode curNext = cur.next; cur.next = slow; slow = cur; cur = curNext; } // 3.一个向后遍历一个向前遍历 while (slow != head) { if (slow.val != head.val) { return false; } if (head.next == slow) { return true; } head = head.next; slow = slow.next; } return true; } }
运行结果： 
