Check if a Singly Linked List is a Palindrome in Python

When it is required to check if a singly linked list is a palindrome or not, methods to add an element, get the previous node and to check if a palindrome is formed are defined.

Below is a demonstration of the same −

Example

 Live Demo

class Node:
   def __init__(self, data):
      self.data = data
      self.next = None

class LinkedList_struct:
   def __init__(self):
      self.head = None
      self.last_node = None

   def add_elements(self, data):
      if self.last_node is None:
         self.head = Node(data)
         self.last_node = self.head
      else:
         self.last_node.next = Node(data)
         self.last_node = self.last_node.next

   def get_previous_node(self, ref_node):
      curr = self.head
      while (curr and curr.next != ref_node):
         curr = curr.next
         return curr

def check_palindrome(my_list):
   beg = my_list.head
   end = my_list.last_node
   while (beg != end and end.next != beg):
      if beg.data != end.data:
         return False
      beg = beg.next
      end = my_list.get_previous_node(end)
   return True

my_instance = LinkedList_struct()

my_input = input('Enter elements to the linked list: ').split()
for data in my_input:
   my_instance.add_elements(int(data))

if check_palindrome(my_instance):
   print('The linked list is palindromic in nature')
else:
   print('The linked list is not palindromic in nature')

Output

Enter elements to the linked list: 89 90 78 90 89
The linked list is palindromic in nature

Explanation

• The ‘Node’ class is created.

• Another ‘LinkedList_struct’ class with required attributes is created.

• It has an ‘init’ function that is used to initialize the first element, i.e the ‘head’ to ‘None’ and last node to ‘None’.

• Another method named ‘add_elements’ is defined, that is used to fetch the previous node in the linked list.

• Another method named ‘get_previous_node’ is defined that is used to display the linked list data on the console.

• A method named ‘check_palindrome’ is defined, that compares the first and last element, if they are not same, it determines that the list wasn’t palindromic in nature.

• An object of the ‘LinkedList_struct’ class is created.

• The user input is taken for the elements in the linked list.

• The elements are added to the linked list.

• The ‘check_palindrome’ method is called on this linked list.

• Relevant output is displayed on the console.