# Check if a Linked list of Strings form a Palindrome

Difficulty Level Easy

## Problem Statement

In the “Check if a Linked list of Strings form a Palindrome” problem we have given a linked list handling string data. Write a program to check whether the data forms a palindrom or not.

## Example

`ba->c->d->ca->b`
`1`

Explanation: In the above example we can see that the string “bacdcab” is a palindrome

## Approach

Given a linked list in which each node contains a string. We have to check if the data in the linked list form a palindrome. A string is a palindrome if it reads the same forwards as it does backward. For example, the number “bacdcab” is a palindrome. A linked list forms palindromes if they have the same order of elements when traversed forwards and backward​.

## Algorithm

1. Initialize an empty string.
2. Traverse the linked list and store all the elements in the linked list in that string.
3. Traverse the linked list to check whether its respective first and last characters are equal or not. If at some point they are not equal then this will not form a palindrome.

## Implementation

### C++ Program to Check if a Linked list of Strings form a Palindrome

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

public:
struct ListNode {
ListNode *next;
string val;
ListNode(string a): next(NULL), val(a){}
};

}

ListNode *node = new ListNode(val);
}

bool isPlalindrome(){
string str = "";
while(ptr){
str+=ptr->val;
ptr = ptr->next;
}
int n = str.size();
for(int i=0;i<n/2;i++){
if(str[i]!=str[n-i-1]){
return false;
}
}
return true;
}

void print_list(){
while(node){
cout<<node->val<<" ";
node = node->next;
}
cout<<endl;
}
};

int main(){

cout<<list->isPlalindrome();
}```

### Java Program to Check if a Linked list of Strings form a Palindrome

```import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{

public static void main (String[] args) throws java.lang.Exception{

System.out.println(obj.isPalindrome());
}

class Node{
Node next = null;
String val = "";

public Node(String val){
this.val = val;
}
}

private int size;

this.size = 0;
}

Node node = new Node(val);
if(this.size == 0){
}
else{
}
this.size++;
}

public boolean isPalindrome(){
String str="";
while(curr!=null){
str+=curr.val;
curr = curr.next;
}

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

public void printList(){
while(curr!=null){
System.out.print(curr.val+" ");
curr = curr.next;
}
System.out.println("");
}

}
}```
`1`

## Complexity Analysis

### Time Complexity

O(n) where n is the number of nodes present in the given linked list. Here we add all the values in a string and check for that string for palindrome condition.

### Space Complexity

O(n) because we use a string formed by concatenating all the node’s values of a given lined list.

Translate »