Given a singly linked list head, write a program to determine if its a palindrome.

Problem Note

• The linked list consists of digits from 0-9.
• Try doing this without using extra space.
• Return 1 if its a palindrome, else 0.

Example 1

Input: 4->5->4
Output: 1
Explanation: The list is palindrome, so the output is 1.

Example 2

Input: 8
Output: 1
Explanation: A single element is always palindrome.

Example 3

Input: 2->5->5->2
Output: 1
Explanation: The given singly linked list is palindrome, so return 1.

Example 4

Input: 2->1
Output: 0
Explanation: The list is not palindrome, so the output is 0.