Check if a Linked list of Strings form a Palindrome

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;

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

    MyLinkedList():head(NULL) {
    }
    
    void addAtHead(string val) {
        ListNode *node = new ListNode(val);
        node->next = head;
        head = node;
    }
    
    bool isPlalindrome(){
    	string str = "";
    	ListNode* ptr = head;
    	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(){
    	ListNode* node = head;
    while(node){
      cout<<node->val<<" ";
      node = node->next;
    }
        cout<<endl;
  }
};

int main(){
  MyLinkedList *list = new MyLinkedList();
  list->addAtHead("b");
  list->addAtHead("ca");
  list->addAtHead("d");
  list->addAtHead("c");
  list->addAtHead("ba");
  
  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{
    
    MyLinkedList obj = new MyLinkedList();
    obj.addAtHead("b");
    obj.addAtHead("ca");
    obj.addAtHead("d");
    obj.addAtHead("c");
    obj.addAtHead("ba");
    
    System.out.println(obj.isPalindrome());
  }
  
  public static class MyLinkedList {
    
      class Node{
          Node next = null;
          String val = "";
          
          public Node(String val){
              this.val = val;
          }
      }
      
      private Node head;
      private int size;

      public MyLinkedList() {
          this.head = null;
          this.size = 0;
      }
      
      
      public void addAtHead(String val) {
          Node node = new Node(val);
          if(this.size == 0){
              this.head = node;
          }
          else{
              node.next = this.head;
              this.head = node;
          }
          this.size++;
      }
      
    public boolean isPalindrome(){
      String str="";
      Node curr = head;
      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(){
      Node curr = head;
      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.