Given a singly linked list of size N of integers. The task is to check if the given linked list is palindrome or not.
Example 1:
Input:
N = 3
value[] = {1,2,1}
Output: 1
Explanation: The given linked list is
1 2 1 , which is a palindrome and
Hence, the output is 1.
Example 2:
Input:
N = 4
value[] = {1,2,3,4}
Output: 0
Explanation: The given linked list
is 1 2 3 4 , which is not a palindrome
and Hence, the output is 0.
Your Task:
The task is to complete the function isPalindrome() which takes head as reference as the only parameter and returns true or false if linked list is palindrome or not respectively.
Expected Time Complexity: O(N)
Expected Auxialliary Space Usage: O(1)  (ie, you should not use the recursive stack space as well)
Constraints:
1 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3
'''
	Your task is to check if given linkedlist
	is a pallindrome or not.
	
	Function Arguments: head (reference to head of the linked list)
	Return Type: boolean , no need to print just return True or False.

	{
		# Node Class
		class Node:
		    def __init__(self, data):   # data -> value stored in node
		        self.data = data
		        self.next = None
	}

	Contributed By: Nagendra Jha
'''
#Function to check whether the list is palindrome.
class Solution:
    def isPalindrome(self, head):
        #code here

Solutions:
class Solution:

	def isPalindrome(self, head):
		fast = head
		slow = head
		while fast and fast.next:
			fast = fast.next.next
			slow = slow.next
		prev = None
		while slow:
			temp = slow.next
			slow.next = prev
			prev = slow
			slow = temp
		(left, right) = (head, prev)
		while right:
			if left.data != right.data:
				return False
			left = left.next
			right = right.next
		return True


class Solution:

	def isPalindrome(self, head):

		def _convert_linked_to_list(head):
			holder = []
			this_node = head
			while this_node:
				holder.append(this_node.data)
				this_node = this_node.next
			return holder
		converted_list = _convert_linked_to_list(head)
		if converted_list != converted_list[::-1]:
			return False
		return True


class Solution:

	def isPalindrome(self, head):
		l = []
		temp = head
		while temp != None:
			l.append(temp.data)
			temp = temp.next
		c = ''
		for i in range(len(l)):
			c += str(l[i])
		if int(c) == int(c[::-1]):
			return 1
		return 0


class Solution:

	def getreverse(self, head):
		prev = None
		curr = head
		forward = curr.next
		while curr is not None:
			curr.next = prev
			prev = curr
			curr = forward
			if forward is not None:
				forward = forward.next
		head = prev
		return head

	def isPalindrome(self, head):
		if head == None or head.next == None:
			return True
		temp = head
		count = 0
		while temp != None:
			count += 1
			temp = temp.next
		if count % 2 != 0:
			i = 1
			j = count // 2
			temp = head
			while i < j + 1:
				temp = temp.next
				i += 1
			middle = temp
		else:
			i = 1
			j = count // 2
			prev = None
			temp = head
			while i <= j:
				prev = temp
				temp = temp.next
				i += 1
			middle = prev
		middle.next = self.getreverse(middle.next)
		temp1 = head
		temp2 = middle.next
		while temp2 != None:
			if temp1.data != temp2.data:
				return False
			temp1 = temp1.next
			temp2 = temp2.next
		return True


class Solution:

	def isPalindrome(self, head):
		l = []
		while head is not None:
			l.append(head.data)
			head = head.next
		if l == l[::-1]:
			return True
		else:
			return False


class Solution:

	def isPalindrome(self, head):

		def rev(head):
			prev = None
			cur = head
			while cur is not None:
				ne = cur.next
				cur.next = prev
				prev = cur
				cur = ne
			return prev

		def midpoint(head):
			count = 0
			cur = head
			while cur is not None:
				cur = cur.next
				count += 1
			return count
		count = midpoint(head)
		if count % 2 == 0:
			n = int(count / 2)
		else:
			n = int(count / 2) + 1
		cur = head
		for i in range(n):
			cur = cur.next
		cur2 = rev(cur)
		cur = head
		while cur is not None and cur2 is not None:
			if cur.data != cur2.data:
				return False
			cur = cur.next
			cur2 = cur2.next
		return True


class Solution:

	def isPalindrome(self, head):
		if not head:
			return None
		stack = []
		node = head
		while node:
			stack.append(node.data)
			node = node.next
		reversed_stack = stack[::-1]
		return stack == reversed_stack


class Solution:

	def isPalindrome(self, head):
		temp = head
		l = 0
		while temp != None:
			l += 1
			temp = temp.next
		temp = head
		ss = []
		mid = l // 2
		for i in range(mid):
			ss.append(temp.data)
			temp = temp.next
		if l % 2 != 0:
			temp = temp.next
		for i in range(mid):
			if ss[-1] == temp.data:
				ss.pop()
				temp = temp.next
			else:
				return False
		return True


class Solution:

	def isPalindrome(self, head):
		fast = head
		slow = head
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
		z = slow.next
		slow.next = None
		temp = z
		A = None
		B = z
		C = None
		while B:
			C = B.next
			B.next = A
			A = B
			B = C
		l = A
		while l and head:
			if l.data != head.data:
				return False
			l = l.next
			head = head.next
		return True


class Solution:

	def isPalindrome(self, head):
		l = []
		while head != None:
			l.append(head.data)
			head = head.next
		if l == l[::-1]:
			return 1
		else:
			return 0


class Solution:

	def isPalindrome(self, head):
		st = []
		curr = head
		isplain = True
		while curr:
			st.append(curr.data)
			curr = curr.next
		curr = head
		while curr != None:
			i = st.pop()
			if curr.data != i:
				isplain = False
				break
			curr = curr.next
		return isplain


def reverseList(head):
	prev = None
	curr = head
	while curr:
		nextNode = curr.next
		curr.next = prev
		prev = curr
		curr = nextNode
	return prev

class Solution:

	def isPalindrome(self, head):
		slow = head
		fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		secondHalf = reverseList(slow)
		firstHalf = head
		while secondHalf:
			if firstHalf.data != secondHalf.data:
				return False
			firstHalf = firstHalf.next
			secondHalf = secondHalf.next
		return True


class Solution:

	def isPalindrome(self, head):
		stack = []
		current = head
		while current is not None:
			stack.append(current)
			current = current.next
		prev = head
		while stack:
			n = stack.pop()
			if prev.data != n.data:
				return 0
			prev = prev.next
		return 1


class Solution:

	def isPalindrome(self, head):
		fast = head
		slow = head
		while fast.next != None and fast.next.next != None:
			slow = slow.next
			fast = fast.next.next
		prev = None
		front = slow.next
		while front != None:
			temp = front.next
			front.next = prev
			prev = front
			front = temp
		slow.next = prev
		head1 = head
		head2 = slow.next
		while head2 is not None:
			if head1.data != head2.data:
				return False
			head1 = head1.next
			head2 = head2.next
		return True


class Solution:

	def isPalindrome(self, head):
		a = []
		while head is not None:
			a.append(head.data)
			head = head.next
		if a == a[::-1]:
			return 1
		else:
			return 0


class Solution:

	def isPalindrome(self, head):
		stack = []
		temp = head
		while temp:
			x = temp.data
			stack.append(x)
			temp = temp.next
		temp = head
		while temp:
			if temp.data == stack[-1]:
				stack.pop()
			temp = temp.next
		if stack == []:
			return 1
		return 0


class Solution:

	def isPalindrome(self, head):

		def reverse(head):
			itr = head
			prev = None
			while itr:
				nxt = itr.next
				itr.next = prev
				prev = itr
				itr = nxt
			return prev
		dummy = Node(0)
		tmp = dummy
		itr = head
		l = 0
		while itr:
			tmp.next = Node(itr.data)
			tmp = tmp.next
			itr = itr.next
			l += 1
		head1 = dummy.next
		head2 = reverse(head)
		k = 0
		while k < l // 2:
			if head1.data != head2.data:
				return False
			head1 = head1.next
			head2 = head2.next
			k += 1
		return True


class Solution:

	def isPalindrome(self, head):
		a = ''
		temp = head
		while temp:
			a = a + str(temp.data)
			temp = temp.next
		if a == a[::-1]:
			return 1
		else:
			return 0


class Solution:

	def isPalindrome(self, head):
		a = []
		while head:
			a.append(head.data)
			head = head.next
		return a == a[::-1]


class Solution:

	def isPalindrome(self, head):

		def reverse(head):
			temp = None
			prev = None
			while head != None:
				temp = head.next
				head.next = prev
				prev = head
				head = temp
			return prev
		slow = head
		fast = head
		while fast != None and fast.next != None:
			slow = slow.next
			fast = fast.next.next
		slow = reverse(slow)
		n1 = head
		n2 = slow
		while n1 != None and n2 != None:
			if n1.data != n2.data:
				return False
			n1 = n1.next
			n2 = n2.next
		return True


class Solution:

	def isPalindrome(self, head):
		curr = head
		st = []
		while curr != None:
			st.append(curr.data)
			curr = curr.next
		curr = head
		while curr != None:
			if st.pop() != curr.data:
				return False
			else:
				curr = curr.next
		return True


class Solution:

	def isPalindrome(self, head):
		li = []
		cur = head
		while cur:
			li.append(cur.data)
			cur = cur.next
		start = 0
		end = len(li) - 1
		while start < end:
			if li[start] != li[end]:
				return False
			start += 1
			end -= 1
		return True


class Solution:

	def getMiddle(self, head):
		slow = head
		fast = head.next
		while fast != None and fast.next != None:
			fast = fast.next.next
			slow = slow.next
		return slow

	def reverse(self, head):
		curr = head
		prev = None
		next = None
		while curr != None:
			next = curr.next
			curr.next = prev
			prev = curr
			curr = next
		return prev

	def isPalindrome(self, head):
		if head.next == None:
			return True
		middle = self.getMiddle(head)
		temp = middle.next
		middle.next = self.reverse(temp)
		head1 = head
		head2 = middle.next
		while head2 != None:
			if head1.data != head2.data:
				return False
			head1 = head1.next
			head2 = head2.next
		return True


class Solution:

	def isPalindrome(self, head):
		dummy = head
		arr = []
		while dummy:
			arr.append(dummy.data)
			dummy = dummy.next
		return arr == arr[-1::-1]


class Solution:

	def isPalindrome(self, head):
		lst = []
		curr = head
		while curr:
			lst.append(curr.data)
			curr = curr.next
		(start, end) = (0, len(lst) - 1)
		while start <= end:
			if lst[start] != lst[end]:
				return False
			start += 1
			end -= 1
		return True


class Solution:

	def rec(self, head):
		if head == None:
			return
		else:
			try:
				self.rec(head.next)
				if self.head.data != head.data:
					if self.Ans:
						self.Ans = False
				self.head = self.head.next
			except:
				return

	def isPalindrome(self, head):
		self.head = head
		self.Ans = True
		temp = self.rec(head)
		return self.Ans


class Solution:

	def isPalindrome(self, head):
		(slow, fast) = (head, head)
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		curr = slow
		temp = None
		prev = None
		while curr:
			temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
		(p1, p2) = (head, prev)
		while p1 and p2:
			if p1.data != p2.data:
				return False
			p1 = p1.next
			p2 = p2.next
		return True


class Solution:

	def isPalindrome(self, head):
		if head == None or head.next == None:
			return True
		(fast, slow) = (head, head)
		while fast and fast.next != None:
			slow = slow.next
			fast = fast.next.next
		(start, mid) = (None, slow)
		while mid:
			end = mid.next
			mid.next = start
			start = mid
			mid = end
		slow = head
		while start and slow and (start != slow):
			if start.data != slow.data:
				return False
			(start, slow) = (start.next, slow.next)
		return True


class Solution:

	def isPalindrome(self, head):
		temp = head
		a = []
		c = 1
		while temp != None:
			a.append(temp.data)
			temp = temp.next
		while head != None:
			i = a.pop()
			if i == head.data:
				c = 1
			else:
				c = 0
				break
			head = head.next
		return c


class Solution:

	def isPalindrome(self, head):
		leftSum = rightSum = 0
		multiplier = 1
		while head:
			leftSum = leftSum + head.data * multiplier
			rightSum = head.data + rightSum * 10
			multiplier *= 10
			head = head.next
		return leftSum == rightSum


class Solution:

	def isPalindrome(self, head):
		l = []
		flag = 0
		temp = head
		while temp:
			l.append(temp.data)
			temp = temp.next
		if l == l[::-1]:
			flag = 1
		else:
			flag = 0
		l.clear()
		if flag == 1:
			return 1
		else:
			return 0


class Solution:

	def isPalindrome(self, head):
		slow = head
		fast = head
		while fast != None and fast.next != None:
			slow = slow.next
			fast = fast.next.next
		curr = slow
		nextn = slow
		prev = None
		while nextn != None:
			nextn = nextn.next
			curr.next = prev
			prev = curr
			curr = nextn
		head2 = prev
		while head2 != None:
			if head.data != head2.data:
				return False
			head = head.next
			head2 = head2.next
		return True


class Solution:

	def isPalindrome(self, head):
		s = ''
		while head != None:
			s += str(head.data)
			head = head.next
		if s == s[::-1]:
			return 1
		return 0


class Solution:

	def isPalindrome(self, head):
		if head == None or head.next == None:
			return True
		(fast, slow) = (head, head)
		while fast != None and fast.next != None:
			fast = fast.next.next
			slow = slow.next
		arr = []
		while slow != None:
			arr.append(slow.data)
			slow = slow.next
		slow = head
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] != slow.data:
				return False
			slow = slow.next
		return True


class Solution:

	def isPalindrome(self, head):
		if head == None or head.next == None:
			return True
		(fast, slow, count) = (head, head, 0)
		while fast != None and fast.next != None:
			fast = fast.next.next
			slow = slow.next
			count += 1
		stack = []
		while slow != None:
			stack.append(slow.data)
			slow = slow.next
		slow = head
		while stack:
			if slow.data != stack.pop():
				return False
			slow = slow.next
		return True


class Solution:

	def isPalindrome(self, head):
		(slow, isPalin) = (head, True)
		stack = []
		while slow != None:
			stack.append(slow.data)
			slow = slow.next
		while head != None:
			i = stack.pop()
			if head.data == i:
				isPalin = 1
			else:
				isPalin = 0
				break
			head = head.next
		return isPalin


class Solution:

	def isPalindrome(self, head):
		stack = []
		cur = head
		while cur:
			stack.append(cur.data)
			cur = cur.next
		if stack == stack[::-1]:
			return 1
		return 0


class Solution:

	def isPalindrome(self, head):
		temp = head
		string = ''
		while temp != None:
			string += str(temp.data)
			temp = temp.next
		if string == string[::-1]:
			return True
		else:
			return False


class Solution:

	def reverse(self, head):
		prev = None
		curr = head
		while curr != None:
			temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
		return prev

	def isPalindrome(self, head):
		if head.next == None:
			return True
		p = head
		k = 0
		while p != None:
			p = p.next
			k += 1
		p = head
		if k % 2 != 0:
			k = k // 2
		else:
			k = k / 2 - 1
		i = k
		while k > 0:
			p = p.next
			k -= 1
		if i != 0:
			p = self.reverse(p.next)
		elif head.next != None and head.data != head.next.data:
			return False
		while p != None:
			if head.data != p.data:
				return False
			head = head.next
			p = p.next
		return True


class Solution:

	def midnode(self, head):
		(slow, fast) = (head, head)
		prev = None
		while fast is not None and fast.next is not None:
			fast = fast.next.next
			prev = slow
			slow = slow.next
		return prev

	def reverse(self, head):
		prev = None
		curr = head
		while curr is not None:
			node = curr.next
			curr.next = prev
			prev = curr
			curr = node
		return prev

	def isPalindrome(self, head):
		midnode = self.midnode(head)
		if midnode is None:
			return True
		right = midnode.next
		left = head
		midnode.next = None
		(currl, currr) = (left, self.reverse(right))
		while currl is not None and currr is not None:
			if currl.data != currr.data:
				return False
			currl = currl.next
			currr = currr.next
		return True


class Solution:

	def isPalindrome(self, head):
		if not head or not head.next:
			return True
		slow = fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		prev = None
		curr = slow
		while curr:
			nxt = curr.next
			curr.next = prev
			prev = curr
			curr = nxt
		ptr1 = head
		ptr2 = prev
		while ptr2:
			if ptr1.data != ptr2.data:
				return False
			ptr1 = ptr1.next
			ptr2 = ptr2.next
		curr = prev
		prev = None
		while curr:
			nxt = curr.next
			curr.next = prev
			prev = curr
			curr = nxt
		return True


class Solution:

	def isPalindrome(self, head):
		li = []
		temp = head
		while temp != None:
			li.append(temp.data)
			temp = temp.next
		li1 = li.copy()
		li1.reverse()
		if li == li1:
			return True
		return False


class Solution:

	def isPalindrome(self, head):
		temp = head
		a = []
		while temp:
			a.append(temp.data)
			temp = temp.next
		if a == a[::-1]:
			return 1
		return 0


class Solution:

	def isPalindrome(self, head):
		temp = head
		s = []
		ispal = True
		while temp != None:
			s.append(temp.data)
			temp = temp.next
		temp1 = head
		while temp1 != None:
			i = s.pop()
			if temp1.data == i:
				ispal = True
			else:
				ispal = False
				break
			temp1 = temp1.next
		return ispal


class Solution:

	def isPalindrome(self, head):
		if head == None or head.next == None:
			return True
		slow = head
		fast = head
		while slow.next != None and fast != None and (fast.next != None) and (fast.next.next != None):
			slow = slow.next
			fast = fast.next.next
		slow.next = self.reverse(slow.next)
		slow = slow.next
		dummy = head
		while slow != None:
			if slow.data != dummy.data:
				return False
			slow = slow.next
			dummy = dummy.next
		return True

	def reverse(self, curr):
		prev = None
		while curr:
			Next = curr.next
			curr.next = prev
			prev = curr
			curr = Next
		return prev


class Solution:

	def isPalindrome(self, head):
		(s, f) = (head, head)
		while True:
			if f.next:
				f = f.next
				if f.next:
					f = f.next
					s = s.next
				else:
					break
			else:
				break
		(prev, rev) = (None, s.next)
		while rev:
			front = rev.next
			rev.next = prev
			prev = rev
			rev = front
		s.next = prev
		(c1, c2) = (head, f)
		while c2:
			if c1.data == c2.data:
				(c1, c2) = (c1.next, c2.next)
			else:
				return False
		return True


class Solution:

	def isPalindrome(self, head):
		values = []
		curr = head
		while curr is not None:
			values.append(curr.data)
			curr = curr.next
		i = 0
		j = len(values) - 1
		while i < j:
			if values[i] != values[j]:
				return False
			i += 1
			j -= 1
		return True


class Solution:

	def isPalindrome(self, head):
		l = []
		temp = head
		while temp != None:
			l.append(temp.data)
			temp = temp.next
		return l == l[::-1]


class Solution:

	def isPalindrome(self, head):
		if head.next is None:
			return 1
		string = ''
		temp = head
		while temp:
			string += str(temp.data)
			temp = temp.next
		if string == string[::-1]:
			return 1
		return 0


class Solution:

	def isPalindrome(self, head):
		slow = head
		fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		prev = 0
		while slow:
			temp = slow.next
			slow.next = prev
			prev = slow
			slow = temp
		slow = head
		fast = prev
		while fast:
			if slow.data != fast.data:
				return False
			slow = slow.next
			fast = fast.next
		return True


class Solution:

	def isPalindrome(self, head):
		a = head
		n = 0
		while a != None:
			a = a.next
			n += 1
		mid = n // 2
		count = 0
		prev = None
		cur = head
		while count < mid:
			prev = cur
			cur = cur.next
			count += 1
		q = cur.next
		cur.next = None
		while q != None:
			temp = Node(q.data)
			prev.next = temp
			temp.next = cur
			cur = temp
			q = q.next
		count = 0
		while count < mid:
			if head.data == cur.data:
				head = head.next
				cur = cur.next
			elif head.data != cur.data:
				return 0
			count += 1
		return 1


class Solution:

	def isPalindrome(self, head):
		temp = head
		c = []
		while temp != None:
			c.append(temp.data)
			temp = temp.next
		b = []
		b = c[::-1]
		if b == c:
			return 1
		else:
			return 0


class Solution:

	def isPalindrome(self, start):
		if start.next is None:
			return 1
		slow = start
		fast = start
		prev = None
		while fast:
			prev = slow
			slow = slow.next
			fast = fast.next
			if fast:
				fast = fast.next
		curr = slow
		prev = None
		while curr:
			forw = curr.next
			curr.next = prev
			prev = curr
			curr = forw
		temp = start
		while prev:
			if prev.data != temp.data:
				return 0
			prev = prev.next
			temp = temp.next
		return 1


class Solution:

	def isPalindrome(self, head):
		slow = head
		fast = head
		while fast and fast.next:
			fast = fast.next.next
			slow = slow.next
		current = slow
		prev = None
		while current:
			nextelement = current.next
			current.next = prev
			prev = current
			current = nextelement
		head1 = head
		lastelement = prev
		while lastelement:
			if head1.data != lastelement.data:
				return False
			else:
				head1 = head1.next
				lastelement = lastelement.next
		return True


class Solution:

	def isPalindrome(self, head):
		arr = []
		while head:
			arr += [head.data]
			head = head.next
		n = len(arr)
		for i in range(n):
			if arr[i] != arr[n - i - 1]:
				return 0
				break
		return 1


class Solution:

	def isPalindrome(self, head):

		def findMid(head1):
			if head1 == None:
				return -1
			if head1.next == None:
				return head1.data
			slow = head1
			fast = head1.next
			while fast.next != None and fast.next.next != None:
				slow = slow.next
				fast = fast.next.next
			return slow

		def reverseList(head3):
			curr = head3
			prev = None
			while curr != None:
				temp = curr.next
				curr.next = prev
				prev = curr
				curr = temp
			return prev
		if head.next == None:
			return 1
		mid = findMid(head)
		head2 = mid.next
		mid.next = None
		head2 = reverseList(head2)
		while head2 != None and head != None:
			if head2.data != head.data:
				return 0
			head2 = head2.next
			head = head.next
		return 1


class Solution:

	def isPalindrome(self, head):
		node = head
		values = []
		while node != None:
			values.append(node.data)
			node = node.next
		l = 0
		r = len(values) - 1
		while l < r:
			if values[l] != values[r]:
				return 0
			l = l + 1
			r = r - 1
		return 1


class Solution:

	def reverseList(self, head):
		prev = None
		current = head
		next = None
		while current != None:
			next = current.next
			current.next = prev
			prev = current
			current = next
		return prev

	def printLinkedList(self, l):
		while l != None:
			print(l.data)
			l = l.next

	def isPalindrome(self, head):
		slow = head
		fast = head
		if head == None:
			return 0
		if head.next == None:
			return 1
		if head.next.next == None:
			if head.data == head.next.data:
				return 1
			else:
				return 0
		while slow.next != None and fast.next != None and (fast.next.next != None):
			slow = slow.next
			fast = fast.next.next
		if fast.next != None:
			nFast = self.reverseList(slow.next)
		else:
			nFast = self.reverseList(slow)
		while nFast != None:
			if nFast.data == head.data:
				nFast = nFast.next
				head = head.next
			else:
				return 0
		return 1


class Solution:

	def isPalindrome(self, head):
		c = 0
		a1 = []
		a2 = []
		itr1 = head
		itr2 = head
		while itr1:
			a1.append(itr1.data)
			c += 1
			itr1 = itr1.next
		while itr2:
			a2.append(itr2.data)
			itr2 = itr2.next
		a2 = list(reversed(a2))
		if a1 == a2:
			return 1
		else:
			return 0


class Solution:

	def isPalindrome(self, head):
		nodes = []
		temp = head
		while temp:
			nodes.append(temp.data)
			temp = temp.next
		(l, r) = (0, len(nodes) - 1)
		while l < r:
			if nodes[l] != nodes[r]:
				return 0
			l += 1
			r -= 1
		return 1


class Solution:

	def isPalindrome(self, head):

		def middle(head):
			slow = head
			fast = head
			while fast.next and fast.next.next:
				slow = slow.next
				fast = fast.next.next
			return slow

		def reverse(head):
			prev = None
			curr = head
			while curr:
				temp = curr.next
				curr.next = prev
				prev = curr
				curr = temp
			return prev
		right1 = middle(head)
		karan = right1.next
		right1.next = None
		right = reverse(karan)
		left = head
		while left and right:
			if right.data != left.data:
				return 0
			right = right.next
			left = left.next
		return 1


class Solution:

	def isPalindrome(self, head):
		if head is None or head.next is None:
			return True
		slow = head
		fast = head
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
		prev = None
		current = slow.next
		while current:
			next_node = current.next
			current.next = prev
			prev = current
			current = next_node
		slow.next = prev
		left = head
		right = slow.next
		while right:
			if left.data != right.data:
				return False
			left = left.next
			right = right.next
		prev = None
		current = slow.next
		while current:
			next_node = current.next
			current.next = prev
			prev = current
			current = next_node
		slow.next = prev
		return True


class Solution:

	def isPalindrome(self, head):
		if head == None:
			return False
		if head.next == None:
			return True
		temp = head
		s1 = ''
		while temp != None:
			s1 += str(temp.data)
			temp = temp.next
		s2 = s1[::-1]
		if s1 == s2:
			return True
		return False


class Solution:

	def isPalindrome(self, head):
		n = head
		stack = []
		isPalin = True
		while n != None:
			stack.append(n.data)
			n = n.next
		while head != None:
			i = stack.pop()
			if head.data == i:
				isPalin = True
			else:
				isPalin = False
				break
			head = head.next
		return isPalin


class Solution:

	def isPalindrome(self, head):
		s = []
		t = head
		while t != None:
			s.append(t.data)
			t = t.next
		while head != None:
			i = s.pop()
			if head.data != i:
				return 0
			head = head.next
		return 1


class Solution:

	def isPalindrome(self, head):
		temp1 = temp2 = head
		while temp1 != None and temp2 != None and (temp2.next != None):
			temp1 = temp1.next
			temp2 = temp2.next.next
		curr = temp1.next
		if curr == None:
			if head.data == temp1.data:
				return True
			else:
				return False
		prev = nextt = None
		while curr != None:
			nextt = curr.next
			curr.next = prev
			prev = curr
			curr = nextt
		temp2 = head
		while prev != None and temp2 != None:
			if prev.data != temp2.data:
				return False
			prev = prev.next
			temp2 = temp2.next
		if temp1.data == temp2.data:
			return True
		else:
			return False


class Solution:

	def isPalindrome(self, head):
		if not head or not head.next:
			return True
		if not head.next.next:
			if head.data == head.next.data:
				return True
			return False
		node = head
		n = 0
		while node:
			n += 1
			node = node.next
		m = n // 2
		mid = head
		if n % 2 == 0:
			m -= 1
		while m > 0:
			mid = mid.next
			m -= 1
		if n % 2 == 0:
			if mid.data != mid.next.data:
				return False
			mid.next = mid.next.next
		end = mid
		cur = head
		prev = None
		while cur != end:
			nxt = cur.next
			cur.next = prev
			prev = cur
			cur = nxt
		node1 = mid.next
		node2 = prev
		while node1 and node2:
			if node1.data != node2.data:
				return False
			node1 = node1.next
			node2 = node2.next
		return True


class Solution:

	def isPalindrome(self, head):
		slow = head
		fast = head.next
		while slow is not None and fast is not None and (fast.next is not None):
			slow = slow.next
			fast = fast.next
			if fast is not None:
				fast = fast.next
		prev = None
		current = slow.next
		while current is not None:
			next = current.next
			current.next = prev
			prev = current
			current = next
		slow.next = prev
		temp = head
		while prev is not None:
			if temp.data != prev.data:
				return False
			prev = prev.next
			temp = temp.next
		return True


class Solution:

	def isPalindrome(self, head):
		if not head or not head.next:
			return True
		slow = head
		fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		prev = None
		curr = slow
		while curr:
			next_node = curr.next
			curr.next = prev
			prev = curr
			curr = next_node
		second_half = prev
		first_half = head
		while second_half:
			if first_half.data != second_half.data:
				return False
			first_half = first_half.next
			second_half = second_half.next
		return True


class Solution:

	def isPalindrome(self, head):
		temp = []
		curr = head
		while curr:
			temp.append(curr.data)
			curr = curr.next
		while head is not None:
			i = temp.pop()
			if head.data != i:
				return False
			head = head.next
		return True


class Solution:

	def isPalindrome(self, head):
		if head == None:
			return 1
		mid = self.middle(head)
		last = self.reverse(mid)
		curr = head
		while last != None:
			if curr.data != last.data:
				return 0
			curr = curr.next
			last = last.next
		return 1

	def middle(self, head):
		slow = head
		fast = head
		while fast != None and fast.next != None:
			slow = slow.next
			fast = fast.next.next
		return slow

	def reverse(self, temp):
		prev = None
		currnode = temp
		nextnode = temp
		while nextnode != None:
			nextnode = nextnode.next
			currnode.next = prev
			prev = currnode
			currnode = nextnode
		temp = prev
		return temp


class Solution:

	def isPalindrome(self, head):
		tmp1 = head
		a = ''
		while tmp1 != None:
			a = a + str(tmp1.data)
			tmp1 = tmp1.next
		s = a[::-1]
		if s == a:
			return True
		else:
			return False


class Solution:

	def isPalindrome(self, head):
		slow = head
		fast = head
		length = 1
		while fast != None and fast.next != None:
			if fast.next.next != None:
				length += 2
			elif fast.next != None:
				length += 1
			temp3 = slow
			slow = slow.next
			fast = fast.next.next
		if length % 2 == 0:
			temp = slow
			temp3.next = None
		else:
			temp = slow.next

		def reverse(head):
			prev = None
			curr = head
			next1 = None
			while curr != None:
				next1 = curr.next
				curr.next = prev
				prev = curr
				curr = next1
			return prev
		head2 = reverse(temp)
		n = head
		m = head2
		while n != None and m != None:
			if n.data != m.data:
				return 0
			n = n.next
			m = m.next
		return 1


class Solution:

	def isPalindrome(self, head):

		def reverselist(head):
			prev = None
			curr = head
			while curr:
				next = curr.next
				curr.next = prev
				prev = curr
				curr = next
			return prev
		slow = fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		if fast:
			slow = slow.next
		slow = reverselist(slow)
		while slow:
			if slow.data != head.data:
				return 0
			slow = slow.next
			head = head.next
		return 1


class Solution:

	def find_mid(self, head):
		slow = head
		fast = head.next
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		return slow

	def reverse(self, head):
		current = head
		prev = None
		while current:
			Next = current.next
			current.next = prev
			prev = current
			current = Next
		return prev

	def isPalindrome(self, head):
		if head == None or head.next == None:
			return True
		temp = head
		slow = self.find_mid(temp)
		head1 = slow.next
		head1 = self.reverse(head1)
		slow.next = None
		while head and head1:
			if head.data != head1.data:
				return False
			head = head.next
			head1 = head1.next
		return True


class Solution:

	def isPalindrome(self, head):
		temp1 = head
		temp2 = head
		pre = head
		while temp2 and temp2.next:
			pre = temp1
			temp1 = temp1.next
			temp2 = temp2.next.next
		temp = temp1
		poin = None
		while temp:
			po = temp.next
			temp.next = poin
			poin = temp
			temp = po
		pre.next = poin
		new = head
		new2 = poin
		while new != poin:
			if new.data != new2.data:
				return False
			new = new.next
			new2 = new2.next
		return True