Palindrome Linked List

Q:
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?
A:
----------------------首先就是空间换时间。 重新生成一个倒置的List ----------------------

public class Solution {
    public boolean isPalindrome(ListNode head) {
        int len=0;
        ListNode header = new ListNode(0);
        ListNode runner = head;
        while(runner != null){
            ListNode tmp = new ListNode(runner.val);
            tmp.next = header.next;
            header.next = tmp;
            runner = runner.next;
        }
        runner = head;
        header = header.next;
        while(runner!=null){
            if(runner.val != header.val)
                return false;
            runner = runner.next;
            header = header.next;
        }
        return true;
    }
}

************* O(1) space + O(n) time **********************
进一步的思考就是：  既然常规办法不能奏效， 就考虑修改List的内容（结构）
得到的方法，就是把前一半逆向插入到后一半 ， 然后再比较
%%%%%%其实也可以取下前一半，逆序，再比较，这样写起来更简单些%%%%%

public class Solution {
    public boolean isPalindrome(ListNode head) {
        int len = 0;
        ListNode header = new ListNode(0);
        header.next = head;
        ListNode tail = header;
        while(tail.next != null){
            len++;
            tail = tail.next;
        }
        // add the first half to the tail of the 
        for(int i =0;i<len/2;i++){
            // detach
            ListNode tmp = header.next;
            header.next = tmp.next;
            // append to tail
            tmp.next = tail.next;
            tail.next = tmp;
        }
        // do comparesion.
        ListNode front = header.next;
        if(len %2 ==1){
            front = front.next;
        }
        tail = tail.next;
        while(tail!=null){
            if(tail.val != front.val)
                return false;
            tail = tail.next;
            front = front.next;
        }
        return true;
    }
}

Mistakes: