Last Updated: Mar 27, 2024

# Check if a Linked List of strings forms a palindrome

## Introduction

Given a linked list having string data, how to check whether the data is palindrome or not? Write a program to check whether the data forms a palindrome or not.

Input  : n -> in -> j -> aaj -> nin -> NULL
Output : True
Explanation: String "ninjaninja" is palindrome.

Input: c -> ode -> c -> d -> NULL
Output : False
Explanation: String "codecd" is not palindrome.

Recommended Topic, Floyds Algorithm

## Intuition

A linked list with a string at each node is given. We need to figure out if the linked list's data is a palindrome. A palindrome is a string that reads the same forward as it does backward. The number "ninjaajnin," for example, is a palindrome. If the elements are in the same order, a linked list produces palindromes when traversed forward and backward.

## Algorithm

1. Create a new empty string.
2. Traverse the linked list and save all of the linked list's elements in that string.
3. Examine the linked list to see if the first and last characters are equivalent. This will not make a palindrome if they are not equal at some point.

Let's check the program to see if a given linked list of strings forms a palindrome.

``````#include <bits/stdc++.h>
using namespace std;

struct Node
{
string value;
Node* next;
};

// Check if str is palinrome
bool isStringPalindrome(string str)
{
int length = str.length();

for (int i=0; i<length/2; i++) {
if (str[i] != str[length-i-1]) {
return false;
}
}
return true;
}

// Check if the linked list is a palindrome.
{
// Add all nodes to form a string
string str = "";
while (node != NULL)
{
str.append(node->value);
node = node->next;
}

return isStringPalindrome(str);
}

Node *newNode(const char *str)
{
Node *new_node = new Node;
new_node->value = str;
new_node->next = NULL;
return new_node;
}

int main()
{

cout<<"true"<<endl;
}
else{
cout<<"false"<<endl;
}

return 0;
}``````

## Complexity Analysis

### Time Complexity

O(n), where n is the number of linked list nodes. All of the values are combined into a string, which is then checked for palindromes.

### Space Complexity

We utilize a string produced by concatenating all of the node values of a specified lined list, therefore it's O(n).

### How is the linked list represented in memory?

The linked list is kept in memory in a scattered way (locations). Each node's memory is allocated dynamically, that is, as and when it is needed. As a result, the linked list may grow as the user desires, and the size is not fixed; it can change.

### How is the linked list different from the array?

An array is a grouping of items of the same data type. A linked list is an ordered collection of elements of the same type with pointers connecting each element to the next.

### How do we check for palindromes in a linked list?

Traverse the linked list and save all of the linked list's elements in that string. Examine the linked list to see if the first and last characters are equivalent. This will not make a palindrome if they are not equal at some point.

### Are linked lists (FIFO) or (LIFO)?

The LinkedList class implements the List, Deque, and Queue interfaces. The first-in, first-out (FIFO) principle governs how a queue stores and removes its components. LinkedList may be used to represent a first-in, first-out (FIFO) queue since it implements the Deque interface.

### Why are linked lists used over arrays?

Linked lists are more efficient than arrays in terms of memory allocation. Unlike arrays, the size of a linked list is not fixed, so it can grow or shrink as the program runs.

## Conclusion

In this article, we took a look at the problem of finding a palindrome in a linked list. We hope that this blog has helped you to solve the problem, and if you would like to learn more, check out the Linked List and Application of Linked List articles on Coding Ninjas Studio. Do upvote our blog to help other ninjas grow. Happy Coding!

Topics covered
1.
Introduction
2.
Intuition
3.
Algorithm
4.
Complexity Analysis
4.1.
Time Complexity
4.2.
Space Complexity
5.