Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome. 

 Example 1: Input: head = [1,2,2,1] 

Output: true 

Example 2: Input: head = [1,2]

 Output: false 

 Constraints: The number of nodes in the list is in the range [1, 105]. 0 <= Node.val <= 9 

 Follow up: Could you do it in O(n) time and O(1) space?

	from collections import deque
	# 1->2->3->4->4->3->2->1
	# b b b b
	# f f f b
	# 1->2->3->4->5->4->3->2->1
	# b b b b b
	# f f f f f
	# Definition for singly-linked list.
	# class ListNode:
	# def __init__(self, val=0, next=None):
	# self.val = val
	# self.next = next
	class Solution:
	arr = []
	def isPalindrome(self, head: ListNode) -> bool:
	stack = deque()
	if (head == None):
	return False
	if (head.next == None):
	return True
	back = head
	front = head
	if(head.next.next == None):
	if(head.val == head.next.val):
	return True
	else:
	return False
	#store all values till mid in linked list to a stack
	while (front.next != None and front.next.next != None):
	stack.append(back.val)
	back = back.next
	front = front.next.next
	if(front.next == None):
	back = back.next
	else:
	temp = back.val
	if(back.next.val != temp):
	return False
	back = back.next.next
	while (back != None):
	poppedval = stack.pop()
	if back.val != poppedval :
	return False
	back = back.next
	return True

view raw palindrom_linkedlist.py hosted with ❤ by GitHub