If O(n) space , just reverse list to another list (list2), and compare them.

If O(1) space, you have to reverse the list in half and compare them , so find the middle is the key point.

Here is my code, I destroy the list ,but you can rebuild it very easily

```
public class Solution {
public boolean isPalindrome(ListNode head) {
ListNode dummy = new ListNode(Integer.MIN_VALUE);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
while( fast != null && fast.next != null ){
slow = slow.next;
fast = fast.next.next;
}
ListNode left = head;
ListNode right = reverse(slow.next);
while(right != null ){
if(left.val != right.val ){
return false;
}
left = left.next;
right = right.next;
}
return true;
}
public ListNode reverse(ListNode node){
if(node == null){
return node;
}
ListNode pre = node;
ListNode cur = node.next;
node.next = null;
while(cur!=null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
```

}