# Check LinkedList for Palindrome

O(n) solution would be to reverse half of the linkedlist and then keep two pointers (starting from the beginning and starting from the mid), keep checking if values in the nodes are same.

You’ll have to be extra carefull with the odd/even length of the linkedlist

class Node(object):

def __init__(self,value):

self.value = value

self.next = None

'''

[1,2,2,1]

l = 4, from l = l/2

[1,2,3,2,1]

l = 5, from l/2+1

'''

class LinkedList(object):

def __init__(self,node):

self.head = node

def getLength(self):

length = 0

current = self.head

while current:

length+=1

current = current.next

return length

def getNodeatK(self,k):

current_length = 0

current = self.head

while current:

current_length+=1

if current_length == k:

return current

current = current.next

def reverseHalf(self):

length = self.getLength()

if length % 2 == 0:

mid = self.getNodeatK(length/2)

else:

mid = self.getNodeatK((length/2)+1)

prev = mid.next

current = prev.next

prev.next = None

while current:

temp = current.next

current.next = prev

prev = current

current = temp

mid.next = prev

def print_ll(self):

current = self.head

while current:

print current.value

current = current.next

def check_palindrome(self):

length = self.getLength()

if length % 2 == 0:

next_pointer = self.getNodeatK((length/2)+1)

else:

next_pointer = self.getNodeatK((length/2)+2)

current = self.head

while current and next_pointer:

if current.value != next_pointer.value:

return False

current = current.next

next_pointer = next_pointer.next

return Trueel1 = Node(1)

el2 = Node(2)

el3 = Node(3)

el4 = Node(2)

el5 = Node(1)el1.next = el2

el2.next = el3

el3.next = el4

el4.next = el5

ll = LinkedList(el1)

ll.reverseHalf()

ll.print_ll()

print ll.check_palindrome()