Symmetric Linked List

Easy

Given the head of a singly linked list, determine whether the sequence of values in the list reads the same forwards and backwards. In other words, check if the linked list exhibits mirror symmetry around its center. A linked list is considered symmetric if the value sequence from the first node to the last node is identical to the sequence from the last node back to the first node. For example, a list containing [3, 7, 4, 7, 3] is symmetric because reading from either direction yields the same sequence. Your task is to return true if the linked list is symmetric, and false otherwise.

Example 1

Input

head = [1,2,2,1]

Output

true

Explanation

Reading the list from head to tail gives [1, 2, 2, 1]. Reading from tail to head also gives [1, 2, 2, 1]. Since both sequences are identical, the list is symmetric.

Example 2

Input

head = [1,2]

Output

false

Explanation

Reading from head to tail gives [1, 2], but reading from tail to head gives [2, 1]. These are different sequences, so the list is not symmetric.

Example 3

Input

head = [1,2,3,2,1]

Output

true

Explanation

This odd-length list has values [1, 2, 3, 2, 1]. The middle element 3 acts as the center of symmetry. Reading in either direction produces the same sequence.

Constraints

The number of nodes in the list is in the range [1, 10⁵].
0 ≤ Node.val ≤ 9