[LeetCode] Palindrome Linked List

This is classic leetcode problem: https://leetcode.com/problems/palindrome-linked-list/

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

Simple solution is to go through the linked list, and put all node reference on a stack, then loop through the stack and linked list at the same time to compare the values. 

public boolean isPalindrome(ListNode head) {
        Stack<Integer> s = new Stack<>();
        ListNode n = head;
        while(n!=null){
            s.push(n.val);
            n = n.next;
        }
        while(head!=null){
            if(head.val != s.pop())
                return false;
            head = head.next;    
        }
        return true;
    }

Follow up:
Could you do it in O(n) time and O(1) space?
This can be done by reversing the half of the linked list. First of all, we need to find the middle point of the list, then reverse the second half, and compare the first half from head and second half from the tail.