给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

解题思路

解法一：
遍历链表，拷贝到数组，再用首尾两个指针依次比较

解法二：
用快慢指针双指针法找到链表的中间节点，再把链表的后一半反转，然后把前一半和后一半依次比较

Java 实现

快慢指针法

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null){
            return  false;
        }
        // 1. 找到前半段的最后一个节点
        ListNode endHalf = endOfFirstHalf(head);
        // 2. 反转后半段
        ListNode startSecondReverse = reverseList(endHalf.next);

        // 3. 比较前后两半
        while (startSecondReverse != null){
            if (head.val != startSecondReverse.val){
                return false;
            }
            head = head.next;
            startSecondReverse = startSecondReverse.next;
        }

        return true;
    }

    private ListNode reverseList(ListNode head) {
        ListNode curr = head;
        ListNode prev = null;
        while (curr != null){
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

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