Palindrome Linked List Detection

Given a singly linked list of integers, determine if it is a palindrome. A linked list is considered a palindrome if it reads the same forward and backward.

Example:

Input:

The given linked list is 1 -> 2 -> 3 -> 2 -> 1 -> NULL.

Output:

true

Explanation:

The linked list is a palindrome because it reads the same when traversed forwards and backwards.

Input:

The first line of input contains an integer 'T', representing the number of test cases. Each test case consists of one line where elements of the singly linked list are separated by a space and end with -1, which is not part of the list.

Output:

For each test case, return "true" or "false" on a new line.

Example:

Input:
2
1 2 3 2 1 -1
1 2 3 -1

Output:
true
false

• 1 ≤ T ≤ 10
• 0 ≤ L ≤ 10⁵
• 1 ≤ data ≤ 10⁹ and data ≠ -1

Note: You do not have to print anything, just implement the given function.

Follow up: Can you solve this in O(N) time complexity and O(1) space complexity iteratively?