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

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

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

}
}```

This problem is selected from LeetCode.

Solution

As we could only use constant extra space, the only solution is to compare the first half and the second half of the linked list node by node. That means we need to reverse the first half of the list, and then compare them.

To reverse only the first half of the list, we could use a fast and a slow pointer. The fast pointer each time steps two nodes in the list. The slow pointer each time steps one node in the list. When the fast pointer reaches the end, the slow pointer is at the middle node. While moving the slow pointer, we could reverse the node right away. After that, we could compare the two halves node by node.

```public boolean isPalindrome(ListNode head) {
return true;

ListNode start = new ListNode(0);

// find the starting points of the first half and
// the second half. Reverse the first half right away.
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next;

start.next = secondHalfStart.next;
secondHalfStart.next = secondHalfStart.next.next;
start.next.next = firstHalfStart;

firstHalfStart = start.next;
}
secondHalfStart = secondHalfStart.next;

// odd number of elements, need to left
// move firstHalfStart one step
if(fast.next == null) {
firstHalfStart = firstHalfStart.next;
}