Leetcode - Palindrome Linked List

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

[分析] 利用two pointers 方式找出链表的中间节点，接着翻转后半段链表，最后比较前后两半，如果完全相同则满足回文性质。注意到比较前后两半时以后半段长度为准，因为链表长度为奇数时，前半段会多一个节点。 Method2 是参考http://blog.csdn.net/u013027996/article/details/46832437的实现，更加简洁，且不需要考虑长度奇数偶数问题，记slow初始标号为1， fast则为2，经过n次循环后，slow=1 + n, fast=2 + 2*n, 第一个while循环结束后，若input链表长度为偶数，则slow.next是后半段链表的起始节点，fast指向最后一个节点；若为奇数，则slow.next最终指向链表的中间节点，fast指向倒数第二个节点。最后判断两段链表是否相同时，若为奇数，则后半段会多一个，但不要紧，因为前半段遍历完while循环即结束。

// Method 2
public class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        ListNode slow = head, fast = slow.next;
        while (fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode curr = slow.next; //p is the start of second half or the middle element
        ListNode next = null;
        ListNode head2 = null;
        while (curr != null) {
            next = curr.next;
            curr.next = head2;
            head2 = curr;
            curr = next;
        }
        while (head != null && head2 != null) {
            if (head.val != head2.val) return false;
            head = head.next;
            head2 = head2.next;
        }
        return true;
    }
}

// Method 1
public class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null)
            return true;
        if (head.next.next == null)
            return head.val == head.next.val ? true : false;
        // split input list
        ListNode p = head, q = head;
        while (q != null) {
            if (q.next != null) {
                if (q.next.next != null) {
                    p = p.next;
                    q = q.next.next;
                } else { // size is even
                    break;
                }
            } else { // size is odd
                break;
            }
        }
        
        // reverse second half
        ListNode prev = null, curr = p.next, next = null;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        // check if is palindrome
        q = prev;
        p = head;
        while (q != null) {
            if (p.val != q.val) return false;
            p = p.next;
            q = q.next;
        }
        return true;
    }
}