Given a singly linked list, determine if it is a palindrome.

Could you do it in O(n) time and O(1) space?

## Solution

1. We can create a new list in reversed order and then compare each node. The time and space are O(n).
2. We can use a fast and slow pointer to get the center of the list, then reverse the second list and compare two sublists. The time is O(n) and space is O(1).

## Code

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
return true;

while(p.next != null){
ListNode temp = new ListNode(p.next.val);
temp.next = prev;
prev = temp;
p = p.next;
}

ListNode p2 = prev;

while(p1!=null){
if(p1.val != p2.val)
return false;

p1 = p1.next;
p2 = p2.next;
}

return true;
}

return true;

//find list center

while(fast.next!=null && fast.next.next!=null){
fast = fast.next.next;
slow = slow.next;
}

slow.next = null;

//reverse second part of the list
ListNode p2 = p1.next;

while(p1!=null && p2!=null){
ListNode temp = p2.next;
p2.next = p1;
p1 = p2;
p2 = temp;
}

//compare two sublists now
ListNode p = (p2==null?p1:p2);