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

Input: 1->2

Output: false

Input: 1->2->2->1

Output: true

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

```public class Program {

public static void Main(string[] args) {
var head = new ListNode(1) {
next = new ListNode(2) {
next = new ListNode(3) {
next = new ListNode(2) {
next = new ListNode(1)
}
}
}
};

Console.WriteLine(res);

Console.WriteLine(res);

}

private static bool IsPalindrome(ListNode head) {
var list = new List<int>();
while(node != null) {
node = node.next;
}
var mid = list.Count / 2;
for(var i = 0; i < mid; i++) {
if(list[i] != list[list.Count - i - 1]) return false;
}
return true;
}

private static bool IsPalindrome2(ListNode head) {
var list = new List<int>();
var list2 = new List<int>();
while(node != null) {
node = node.next;
}
list.Reverse();
for(var i = 0; i < list.Count; i++) {
if(list[i] != list2[i]) return false;
}
return true;
}

public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}

}```

```True
True```