Description:

This program uses the Linked List data structure. We will implement the stack data structure to check if the linked list is a palindrome or not. We traverse the linked list two times.

In the first traversal, every element of the linked list from head to tail is pushed onto the stack.

In the second traversal, we check if each element is equal to the element popped from the top of the stack or not.

If every element during the second traversal is equal to the popped element, then the linked list is a palindrome.

Python Code:

class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.first = None
def insert(self, data):
newNode = Node(data)
if self.first is None:
self.first = newNode
else:
temp = self.first
while temp.next is not None:
temp = temp.next
temp.next = newNode
def display(self):
print("\nLinked List: ", end='')
temp = self.first
while temp is not None:
print(temp.data, end='->')
temp = temp.next
print(None)
def check_palindrome(self):
stack = []
temp = self.first
while temp is not None:
stack.append(temp.data)
temp = temp.next
temp = self.first
while temp is not None:
popped = stack.pop()
if temp.data == popped:
temp = temp.next
else:
return False
return True
def main():
elements = list(map(int, input("Enter elements of the linked list: ").split(' ')))
obj = LinkedList()
for data in elements:
obj.insert(data)
obj.display()
if obj.check_palindrome():
print("Linked List is a Palindrome!")
else:
print("Linked List is not a Palindrome!")
if __name__ == "__main__":
main()

Output 1:

Enter elements of the linked list: 10 20 30 20 10

Linked List: 10->20->30->20->10->None
Linked List is a Palindrome!

Output 2:

Enter elements of the linked list: 10 20 30 40

Linked List: 10->20->30->40->None
Linked List is not a Palindrome!

## Comments