Check If Linked List Is Palindrome

Given a singly linked list of integers, determine if the linked list is a palindrome.

Explanation:

A linked list is considered a palindrome if it reads the same forwards and backwards.

Input:

The first line contains an integer T, representing the number of test cases. For each test case, a single line contains the elements of the linked list separated by spaces, ending with -1. The -1 is not part of the list, and only acts as a terminator.

Output:

For each test case, output "True" if the linked list is a palindrome, otherwise output "False".

Example:

Input:

3
1 2 1 -1
3 4 4 3 -1
1 -1

Output:

True
True
True

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 5 * 104
• -109 ≤ data ≤ 109 and data ≠ -1
• Time Limit: 1sec

Note:

No explicit output printing is required; the implementation should return the result.