[234. Palindrome Linked List] #leetcode

234_0914.java

class Solution {
  // O(n) O(1)
    public boolean isPalindrome(ListNode head) {
        ListNode rev = null, tmp = null;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            tmp = rev;
            rev = head;
            head = head.next;
            rev.next = tmp;
        }
        ListNode tail = (fast != null) ? head.next : head;
        boolean isPali = true;
        while (rev != null) {
            isPali = isPali && rev.val == tail.val;
            tmp = head;
            head = rev;
            rev = rev.next;
            head.next = tmp;
            tail = tail.next;
        }
        return isPali;
    }
}