题目内容

给定一个单链表，链表的每个节点保存一个整数值。若按照从链头到链尾的顺序读取所有节点值，与按照从链尾到链头的顺序读取所有节点值，得到的序列完全一致，则称该链表为回文链表。请判断给定的链表是否属于回文链表。

约束条件：

• 链表中的节点数量 $n$ 满足 $1 \le n \le 10^5$。
• 每个节点的取值满足 $0 \le \text{Node.val} \le 9$。

输入描述

输入包含一个参数：

• head：链表的头节点，类型为单链表节点。每个节点包含一个整数属性 val 和一个指向后继节点的指针 next。

输出描述

返回一个布尔值。如果链表是回文链表，返回 true；否则返回 false。

样例1

输入

1
5

输出

true

说明

链表只有 1 个节点，其值为 5。

从链头到链尾读取的序列是 5，从链尾到链头读取的序列也是 5，两个序列完全一致，因此该链表是回文链表，返回 true。

样例2

输入

5
1 2 3 2 1

输出

true

说明

链表结构为 $1 \to 2 \to 3 \to 2 \to 1$。

从链头到链尾读取，得到的节点值依次是 1、2、3、2、1；从链尾到链头读取，得到的节点值依次也是 1、2、3、2、1。两端配对的值分别为 1 和 1、2 和 2，中间值为 3，因此是回文链表，返回 true。

样例3

输入

6
1 2 3 1 2 3

输出

false

说明

链表结构为 $1 \to 2 \to 3 \to 1 \to 2 \to 3$。

从链头到链尾读取时，第一个节点值是 1，最后一个节点值是 3。从链尾到链头读取时，第一个值会变成 3，第一个值会变成 1，两个序列的对应位置不一致，因此不是回文链表，返回 false。