题目：回文链表
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
- 你能否用
O(n)时间复杂度和O(1)空间复杂度解决此题？
来源：力扣（LeetCode）第234题
链接：https://leetcode-cn.com/problems/palindrome-linked-list
分析：
- 最常见的做法是将链表变为数组，通过数组的随机访问的特性检测回文链表。
- 第二种更为方便的方法是使用快慢双指针找到链表的中点，然后将前半部分的链表翻转。
代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) //两种特殊情况 return true;
ListNode slow = head, fast = head; //快慢指针
while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;} //找到链表的中间位置奇数找到的是正中间，偶数得到的是中间靠右的数
ListNode pre = head.next, next; // 翻转前半链表，pre储存的是后面的结点，next储存的是head翻转后的head.next
while (pre != slow) { // 如果pre等于slow，那么head会指向slow前面的那个数
next = head;head = pre; // 如果实在看不懂的话自己画一下就明白了
pre = head.next;head.next = next;
}
if (fast != null) slow = slow.next; // 如果链表是奇数的长度，那么fast.next == null，这时slow往前移一位
while (head != null && slow != null) { // 检测是否回文
if (head.val != slow.val) return false;
head = head.next;slow = slow.next;
}
return true;
}
}
复杂度分析：