234. [E] Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/

之前去 Facebook 面试遇到过这个题目，基于 206 的反转单链表 可以很容易解决。基本思路就是，从链表中间截断链表，反转后面半截，然后开始比较。

class Solution {
    private int linkLength(ListNode head) {
        int len = 0;
        while(head != null) {
            head = head.next;
            len++;
        }
        return len;
    }
    
    // (..) <- (p)  (c) -> (n) -> (..)
    private ListNode reverseLink(ListNode head) {
        ListNode p = null, c = head, n = null;
        while (c != null) {
            n = c.next;
            c.next = p;
            p = c;
            c = n;
        }
        return p;
    }
    
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        
        int len = linkLength(head);
        ListNode t = head;
        for (int i = 0; i <  len / 2 - 1; i++) {
            t = t.next;
        }
        ListNode tt = t.next;
        t.next = null;
        t = reverseLink(tt);
        
        while (head != null) {
            if (head.val != t.val) {
                return false;
            }
            head = head.next;
            t = t.next;
        }
        return true;
    }
}