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 True
el1 = 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()

Software developer with a passion for writing pragmatic code.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store