剑指 Offer II 027. 回文链表

递归

class Solution {
    ListNode p;
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        p = head;
        return helper(head);
    }
    private boolean helper(ListNode head) {
        if (head == null) return true;
        boolean res = helper(head.next);
        res = res && (head.val == p.val);
        p = p.next;
        return res;
    }
}

快慢指针

1. 使用快慢指针确定中点
2. 反转链表

3. 挨个比对

   class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 奇偶判断
        if (fast != null) slow = slow.next;
        ListNode n2 = reverse(slow);
        while (head != null && n2 != null) {
            if (head.val != n2.val) return false;
            head = head.next;
            n2 = n2.next;
        }
        return true;
    }
    private ListNode reverse(ListNode head) {
        ListNode prev = null, p = head;
        while (p != null) {
            ListNode next = p.next;
            p.next = prev;
            prev = p;
            p = next;
        }
        return prev;
    }
   }