Given a linked list, check whether it is a palindrome.

Examples:

Input:   1 -> 2 -> 3 -> 2 -> 1 -> null

output: true.

Input:   1 -> 2 -> 3 -> null  

output: false.

Requirements:

Space complexity must be O(1)

思路：找到中点，在reverse，比较reverse的一半和以前的一半，是否相同。

public class Solution {
  public boolean isPalindrome(ListNode head) {
    if(head == null || head.next == null) {
      return true;
    }
    ListNode middle = findMiddle(head);
    ListNode right = reverse(middle.next);
    while(right != null) {
      if(head.value != right.value) {
        return false;
      }
      head = head.next;
      right = right.next;
    }
    return true;
  }

  private ListNode findMiddle(ListNode head) {
    if(head == null) {
      return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    return slow;
  }

  private ListNode reverse(ListNode head) {
    if(head == null || head.next == null) {
      return head;
    }
    ListNode newHead = reverse(head.next);
    ListNode tmp = head.next;
    tmp.next = head;
    head.next = null;
    return newHead;
  } 
}