Last Updated on June 15, 2022 by Ria Pathak
Introduction
The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.
Problem Statement
In this problem, we are given a singly linked list of strings. We have to check whether the given data is palindrome or not.
Problem Statement Understanding
Let’s try to understand the problem statement with the help of examples.
Suppose the linked list is:
and now, according to the problem statement, we have to determine whether this linked list of [strings is a palindrome](https://www.prepbytes.com/blog/linked-list/check-if-a-doubly-linked-list-of-characters-is-palindrome-or-not/ “strings is a palindrome”) or not.
- So now, to check the above linked list for palindrome we will have to combine the data of all the nodes, and after combining, we will get a string, and then we will have to check whether this string is a palindrome or not.
- So for the above linked list, the resultant string is aabbaa as we can see, the resultant string is palindrome, so we will print that it is palindrome.
Output: Palindrome
If the given linked list is a → cd → e → ef → a.
- After combining the data of all the nodes for the above linked list, we can see that our resultant string is acdeefa, which is not a palindrome.
Output: Not a Palindrome
Some more examples
Input: cd → ef → fe → dc
Output: Palindrome
Input: a → aab → bce → f
Output: Not a Palindrome
Input: a → aa → bbb → bbb → aa → a
Output: Palindrome
I hope from the above examples the problem is clear, and now the main question is how we should approach this problem?
Note: We cannot use the same approach that we often use while checking if a linked list (simple linked list where each node either contains digits (0-9) or characters (a-z, A-Z)) is palindrome or not because here nodes contain strings as values and these strings can be of different length, so the comparison of the last node with the first node, second last node with the second node and so on will not work here.
To overcome the above problem, we will have to create a single string by combining all the list elements and then check if the string is palindrome.
Let us have a glance at the approach by referring the best sites to learn coding.
Approach
Our approach will be simple:
- We will create a string out of the linked list by traverse the list and appending the value of every node of the list at the end of the string.
- Once we have our string constructed, then we will check whether the string is a palindrome or not.
- If the string is a palindrome, it means that our linked list of strings also forms a palindrome. So we will output Palindrome.
- Otherwise, if the string is not a palindrome, then the linked list of strings also does not form a palindrome, so we will output Not a Palindrome.
Algorithm
- First, we will create an empty string S.
- Now, we will traverse the list and append every element of the list at the end of S. In this way, we are constructing the string S.
- Now, once we have our string S constructed, we will check if this constructed string is palindrome or not:
- If the constructed string S is a palindrome, it means that our linked list of strings also forms a palindrome. So we will output Palindrome.
- Otherwise, if the constructed string S is not a palindrome, then our linked list of strings also does not form a palindrome, so we will output Not a Palindrome.
To check if a string S is palindrome or not
- We will run a loop from 0 to (length/2) (length here denotes the length of the string S).
- Inside this loop, we will check whether the ith character of the string S equals the (length-i-1)th character of the string S (We are comparing the first and last element, then the second and the second last element, and so on).
- If at any point, these two are not equal, we will return false i.e. the string S is not a palindrome.
- Else, at the end of the loop, if all the characters at ith indexes have matched the characters at (length-i-1)th indexes during the loop, we will return true.
DRY RUN
Code Implementation
#include <bits/stdc++.h>
using namespace std;
struct Node
{
string data;
Node* next;
};
bool isPalindromeUtil(string str)
{
int length = str.size();
for (int i=0; i<length/2; i++)
if (str[i] != str[length-i-1])
return false;
return true;
}
bool isPalindrome(Node *node)
{
string str = "";
while (node != NULL)
{
str+=node->data;
node = node->next;
}
return isPalindromeUtil(str);
}
void printList(Node *node)
{
while (node != NULL)
{
cout << node->data << " -> ";
node = node->next;
}
printf("NULL\n");
}
Node *newNode(const char *str)
{
Node *new_node = new Node;
new_node->data = str;
new_node->next = NULL;
return new_node;
}
int main()
{
Node *head = newNode("a");
head->next = newNode("ab");
head->next->next = newNode("ba");
head->next->next->next= newNode("a");
if(isPalindrome(head))
cout<<"Palindrome"<<endl;
else cout<<"Not a Palindrome"<<endl;
return 0;
}
import java.util.Scanner;
class Node
{
String data;
Node next;
Node(String d)
{
data = d;
next = null;
}
}
public class LinkedList_Palindrome
{
Node head;
boolean isPalidromeUtil(String str)
{
int length = str.length();
for (int i=0; i<length/2; i++)
if (str.charAt(i) != str.charAt(length-i-1))
return false;
return true;
}
boolean isPalindrome()
{
Node node = head;
String str = "";
while (node != null)
{
str = str.concat(node.data);
node = node.next;
}
return isPalidromeUtil(str);
}
public static void main(String[] args)
{
LinkedList_Palindrome list = new LinkedList_Palindrome();
list.head = new Node("a");
list.head.next = new Node("ab");
list.head.next.next = new Node("ba");
list.head.next.next.next = new Node("a");
if(list.isPalindrome())
System.out.println("Palindrome");
else System.out.println("Not a Plaindrome");
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def isPalindromeUtil(self, string):
return (string == string[::-1])
def isPalindrome(self):
node = self.head
temp = []
while (node is not None):
temp.append(node.data)
node = node.next
string = "".join(temp)
return self.isPalindromeUtil(string)
def printList(self):
temp = self.head
while (temp):
print(temp.data,end=" ")
temp = temp.next
llist = LinkedList()
llist.head = Node('a')
llist.head.next = Node('ab')
llist.head.next.next = Node("ba")
llist.head.next.next.next = Node("a")
if llist.isPalindrome():
print("Palindrome")
else:
print("Not a palindrome")
Output
Palindrome
[forminator_quiz id=”4444″]
Space Complexity: O(s), where s is the size of the string created.
So, in this article, we have tried to explain the most efficient approach to check if a linked list of strings forms a palindrome. This is an important concept when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.