I came up with this very basic approach, pretty similar with checking palindrome number.

It is just my first try and it works.

Please tell me where I could improve the code and is this the solution that costs O(n) time and O(1) space?

Explanations:

- Find the middle of the list and break the list into two pieces
- Reverse the second half of the list
- Check if very node is the same in same position of each list.
- Since the number of nodes might be odd or even, so the last "if"

checks are meant to deal with two different situations.

```
public boolean isPalindrome(ListNode head) {
if(head==null) {
return true;
}
ListNode l1 = head;
ListNode nodeBeforeMid = findMid(head);
ListNode l2 = nodeBeforeMid.next;
nodeBeforeMid.next = null;
l2 = reverseList(l2);
while(l1!=null && l2!=null && l1.val==l2.val) {
l1 = l1.next;
l2 = l2.next;
}
if(l1==null && l2==null) {
return true;
}
else if(l1==null && l2!=null) {
return true;
}
return false;
}
public ListNode findMid(ListNode head) {
ListNode slow = new ListNode(0);
slow.next = head;
ListNode fast = new ListNode(0);
fast.next = head;
while(fast.next!=null && fast.next.next!=null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public ListNode reverseList(ListNode head) {
ListNode nHead = null;
while(head!=null) {
ListNode temp = head.next;
head.next = nHead;
nHead = head;
head = temp;
}
return nHead;
}
```