Palindrome Linked List Problem Statement

You are provided with a singly linked list of integers. Your task is to determine whether the given singly linked list is a palindrome. Return true if it is a palindrome, otherwise return false.

Example:

Input:

1 -> 2 -> 3 -> 2 -> 1 -> NULL

Output:

true

Explanation:

The given linked list maintains the same sequence of elements when traversed forwards and backwards, hence it is a palindrome.

Constraints:

• 1 <= T <= 10
• 0 <= L <= 10^5
• 1 <= data <= 10^9 (and data != -1)

Input:

The first line of input contains an integer 'T' representing the number of test cases. For each test case, the only line contains the elements of the singly linked list separated by a space, ending with -1. Note that -1 is not part of the list.

Output:

For each test case, output 'true' or 'false' in a new line, indicating whether the linked list is a palindrome or not.

Note:

You do not need to print anything as it is managed within the implementation. Simply complete the provided function.

Follow Up:

Can you devise a solution with O(N) time complexity and O(1) space complexity iteratively?