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.