Implement a function to check if a linked list is a palindrome.

Example

Given 1->2->1, return true

Challenge

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

Solution

public class Solution {
    /**
     * @param head a ListNode
     * @return a boolean
     */
    public boolean isPalindrome(ListNode head) {

        // get half
        ListNode runner = head;
        ListNode walker = new ListNode(0);
        walker.next = head;
        while(runner != null && runner.next != null) {
            runner = runner.next.next;
            walker = walker.next;
        }

        // reverse half tail
        ListNode tail = null;
        ListNode move = walker.next;

        while(move!=null){
            ListNode next = move.next;
            move.next = tail;
            tail = move;
            move = next;
        }

        // check palindrome
        while(head != null&& tail != null) {
            if(head.val != tail.val)
                return false;
            head = head.next;
            tail = tail.next;
        }
        return true;
    }
}