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

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

My solution:

Use a list to store the values in the link, and most common 2 pointer way to find pairs.
For Integer type in list, you can only compare 2 values using int Integer.compareTo()

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while(head!=null){
            list.add(head.val);
            head=head.next;
        }
        int i=0,j=list.size()-1;
        while(i<j){
            if(list.get(i).compareTo(list.get(j))!=0) return false;
            i++;j--;
        }
        return true;
    }
}

Solution 1:

Reversed first half == Second half?

Phase 1: Reverse the first half while finding the middle.
Phase 2: Compare the reversed first half with the second half.

(slow.next,)

That first evaluates the right side and then assigns to the left side from left to right. So first, slow becomes what used to be slow.next. And then, slow.next gets assigned something, but that slow is already changed! So you’re setting the .next of the wrong node. That’s the difference to the first version.

``` python
def isPalindrome(self, head):
    rev = None
    slow = fast = head
    while fast and fast.next:
        fast = fast.next.next
        rev, rev.next, slow = slow, rev, slow.next
    if fast:
        slow = slow.next
    while rev and rev.val == slow.val:
        slow = slow.next
        rev = rev.next
    return not rev

Source

Another Java Solution:

Source