1.题目

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

示例 1：

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

示例 2：

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

提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list

2.思路

（1）双指针——将值复制到数组中
由于单链表无法倒着遍历，故可以先将链表中的值复制到数组中，然后再使用双指针法判断是否为回文即可。该方法的时间复杂度和空间复杂度均为O(n)。
（2）双指针——快慢指针
① 通过快慢指针 fast 和 slow 找到链表的中点；
② 从 slow 指针开始反转后面的链表；
③ 最后使用双指针判断回文即可。

3.代码实现（Java）

//思路1————双指针——将值复制到数组中
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> values = new ArrayList<Integer>();
        //将链表中的值复制到数组values中
        ListNode curNode = head;
        while (curNode != null) {
            values.add(curNode.val);
            curNode = curNode.next;
        }     
        //使用双指针判断回文
        int left = 0, right = values.size() - 1;
        while (left < right) {
        	//在比较Integer类型的值时，使用equals()比较更合适
            if (!values.get(left).equals(values.get(right))) {
                return false;
            } else {
            	//移动指针
                left++;
                right--;
            }
        }
        return true;
    }
}

//思路2————双指针——快慢指针
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        //通过快慢指针找到链表的中点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //如果fast指针没有指向null，说明链表⻓度为奇数，slow还要再前进⼀步
        if (fast != null) {
            slow = slow.next;
        }
        //从slow指针开始反转后面的链表
        ListNode left = head, right = reverse(slow);
        //使用双指针判断回文
        while (right != null) {
            if (left.val != right.val) {
                return false;
            } else {
                //移动指针
                left = left.next;
                right = right.next;
            }
        }
        return true;
    }
    
    //反转以head为头结点的链表
    public ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head, nxt = head;
        while (cur != null) {
            nxt = cur.next;
            // 逐个结点反转
            cur.next = pre;
            // 更新指针位置
            pre = cur;
            cur = nxt;
        }
        // 返回反转后的头结点
        return pre;
    }
}