[编程题]回文链表

从两边往中间比:递归到最后一个再开始比较

private  ListNode head = null;
public  boolean isPalindrome(ListNode pHead) {
    if (head == null) head = pHead;
    if (pHead.next == null) return head.val == pHead.val;
    boolean palindrome = isPalindrome(pHead.next);
    head = head.next;
    return palindrome && head.val == pHead.val;
}

从中间往两边比：快慢指针，速度1:2算出中间值

 public boolean isPalindrome(ListNode pHead) {
    if (pHead.next == null) return true;    // 一个数
    return toCompare(pHead, pHead.next.next) != null;
}
// 如果是，返回最后一个数
private  ListNode toCompare(ListNode left, ListNode next) {
    if (next == null) return left.next; //偶数
    if (next.next == null) return left.next.next;// 奇数
    ListNode right = toCompare(left.next, next.next.next);
    if (right == null) return null;
    if (left.next.val == right.val) 
        return right.next == null? right:right.next; // 返回最后一个数
    else return null;
}