Problem: Write a python program to check if a linked list is a palindrome or not.
What is Palindrome?
A palindrome can be a number, a word, a phrase, or a sequence of characters that is the same from front and back. Let's see the image below for a better understanding.
Method 1: Reverse and Compare method.
Method 2: Using Stack.
Method 3: Using Recursion.
Check if a linked list palindrome or not using Reverse and Compare method
In this method, you need to follow the simple steps given below.
Steps:
- Reverse the linked list and store each data into another linked list.
- Start from the head node and compare each node from both linked lists.
- If the two node values from the two linked lists are not matched return false, otherwise return true.
See the diagram for a better understanding.
The Code
'''
Write a python program to check a linked list is a palindrome or not.
Using the Reverse & Compare method.
'''
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def addNode(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def isEqual(self, flist, slist):
while(flist != None and slist != None):
if (flist.data != slist.data):
return False
flist = flist.next
slist = slist.next
return True
def checkpalindrome(self):
'''
Here we're creating the second linked list to store the data
of the first linked list in the reverse order.
'''
self.temp = LinkedList()
node = self.head
while(node != None):
temp = self.temp.addNode(node.data)
node = node.next
return self.isEqual(self.head, self.temp.head)
def printNode(self):
temp = self.head
while(temp):
print(temp.data, end='->')
temp = temp.next
print("\n")
if __name__ == "__main__":
# Declare an object of LinkedList class
obj = LinkedList()
obj.addNode(1)
obj.addNode(2)
obj.addNode(3)
obj.addNode(2)
obj.addNode(1)
print("The Linked List is: ")
obj.printNode()
if obj.checkpalindrome():
print("The Linked List is a palindrome")
else:
print("The Linked List is not a palindrome")
Output
Example 1:
The Linked List is:
1->2->3->2->1->
The Linked List is a palindrome
Example 2:
The Linked List is:
1->2->2->1->
The Linked List is a palindrome
Example 3:
The Linked List is:
2->3->2->1->
The Linked List is not a palindrome
Complexity Analysis
Since the total number of nodes is n,
Time Complexity: O(n)
Space Complexity: O(n)
Check if a linked list is a palindrome or not using Stack
Points to be remember
1. A stack is a type of data structure that is used to store different types of objects. For example, numbers, characters, words, etc.
2. Items are added to the stack using push operation and retrieved by pop operation.
3. Stack follows LIFO order. That means items entered into the stack, at last, are removed at first.
Now come to the main topic. We know if a linked list is a palindrome then the front half of the linked list is the same as the reverse of the second half. Here we will use a stack to solve the problem using this logic.
Let's see the steps given below.
Steps:
- Possibility #1: We know the length of the linked list.
- Iterate through the linked list until the middle node comes and store each node value into a stack.
- If the length of the linked list is odd then jump to the next node from the present node and follow the next steps or if the length is even then simply follow the next steps.
- pop each item from the top of the stack(where we stored the values up to the middle node of the linked list) and compare it with the respective node of the linked list.
- If items are not matched, return False otherwise return True.
- Possibility #2: We don't know the length of the linked list.
- Implement two runners, 'slow' and 'fast', pointed to the head of the linked list. Here 'fast' is 2x faster than the 'slow'.
- Iterate through the linked list using a loop and push the data from the 'slow'. When 'fast' hits the end, at the same time 'slow' hits the middle. Now follow the same step described in the previous, pop the top element from the stack and, compare.
See this diagram for a better understanding.
The Code
'''Check if a linked list is a palindrome or not
using stack in python'''
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def addNode(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def checkpalindrome(self):
slow = self.head
fast = self.head
stack = []
while(fast != None and fast.next != None):
stack.append(slow.data)
slow = slow.next
fast = fast.next.next
if fast != None:
slow = slow.next
while(slow != None):
top = stack.pop()
if(top != slow.data):
return False
slow = slow.next
return True
def printNode(self):
temp = self.head
while(temp):
print(temp.data, end='->')
temp = temp.next
print("\n")
if __name__ == "__main__":
obj = LinkedList()
obj.addNode(1)
obj.addNode(2)
obj.addNode(3)
obj.addNode(2)
obj.addNode(2)
print("The Linked List is: ")
obj.printNode()
if obj.checkpalindrome():
print("The Linked List is a palindrome")
else:
print("The Linked List is not a palindrome")
Output
The Linked List is:
2->2->3->2->1->
The Linked List is not a palindrome
Complexity Analysis
Since the total number of nodes is n,
Time Complexity: O(n)
Space Complexity: O(n/2)
Check if a linked list palindrome or not using recursion
Now we will solve the problem using recursion methods. In this case, we will be comparing element 0 with the element (n-1), element 1 with the element (n-2), and so on until the middle node comes.
Have a look at the diagram below.
The Code
'''
Write a python program to check a linked list is a
palindrome or not. Solve the problem using recursion.
'''
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def addNode(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def isPalindrome(self):
stack = []
return self.isPalindromeUtil(stack, self.head, self.head)
def isPlaindromeCheck(self, stack, slow, fast):
if fast != None:
slow = slow.next
while slow != None:
top = stack.pop()
if (top != slow.data):
return False
slow = slow.next
return True
def isPalindromeUtil(self, stack, slow, fast):
if fast != None:
if fast.next == None:
st = self.isPlaindromeCheck(stack, slow, fast)
return st
elif fast == None:
st = self.isPlaindromeCheck(stack, slow, fast)
return st
stack.append(slow.data)
res = self.isPalindromeUtil(stack, slow.next, fast.next.next)
if res != False:
return True
return res
def printNode(self):
temp = self.head
while(temp):
print(temp.data, end='->')
temp = temp.next
print("\n")
if __name__ == "__main__":
obj = LinkedList()
obj.addNode(1)
obj.addNode(2)
obj.addNode(4)
obj.addNode(3)
obj.addNode(4)
obj.addNode(2)
obj.addNode(1)
print("The Linked List is: ")
obj.printNode()
if obj.isPalindrome():
print("The Linked list is a palindrome")
else:
print("The Linked list is not a palindrome")
Output
The Linked List is:
1->2->4->3->4->2->1->
The Linked list is a palindrome
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n/2)