Check LinkedList for Palindrome
1 min readMay 22, 2016
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()
