Check if a linked list of strings forms a palindrome

By | September 20, 2016
Check if a linked list of strings forms a palindrome

                                                                       Check if a linked list of strings forms a palindrome

Each node represents strings in a given linked list.Now the query is,whether linked list of strings form’s palindrome or not ? By Defination String is a palindrome if the reverse of that string is equal to the original string.I believe in giving examples than more explanation.

Let’s Get an idea by going through the 5 Examples.

Example 1:
Input:- T -->op--> spo-->t
Output:- true
If we combine the all the characters in the String:topspot

Example 2:
Input:- M-->y--> g-->ym
Output:- true
If we combine the all the characters in the String:My gym

Example 3:
Input:- I -->did,--> did-> I
Output:- true
If we combine the all the characters in the String:I did, did I

Example 4:
Input:- Ta-->ttarr-->atta-->t
Output:- true
If we combine the all the characters in the String:Tattarrattat

Example 5:
Input:- Sai-->p->pua-->kivik-->au-->pp-->ias
Output:- true
If we combine the all the characters in the String:Saippuakivikauppias

Main Logic Behind the Program:

We actually club all the Nodes data into Single String.Once,we get the String, we try to check each character by character with its equal length character from the end.

Complete Program,here i have compiled and executed using steps mentioned in the Article.


#include <bits/stdc++.h>;
#include <string.h>;
using namespace std;
// Structure of node.It contains two elements.one is string.
// Second one is Pointer to Node

struct node
{
    string data;
    struct node* next;
};

/* Function to create a new node with given data */
node* newNode(string str)
{
    node *new_node = new node;
    new_node->data = str;
    new_node->next = NULL;
    return new_node;
}

node* GenerateLinkedList(int n)
{
    string myString;
    int i;

    struct node *temp;
    struct node *headtemp;
    struct node *head;
    struct node *newlycreatednode;

    printf("Enter the data of first node:-\n\n");
    cin <<myString;
    cout <<endl<<endl;

    head = newNode(myString);

    head->data = myString;
    head->next = NULL;


    temp = head;

    //this loop will be executed,if it is more than 2 nodes.
    for(i=2; i<=n; i++)
    {
       myString.clear();
       printf("Enter the data of %d node:-\n\n",i);
       cin >> myString;
       cout <<endl<<endl;
       newlycreatednode = newNode(myString);
       newlycreatednode->next = NULL;

       temp->next = newlycreatednode;
       temp = temp->next;
    }
    
    printf("Linked List Created with nodes - %d successfully \n\n",n);

    return head;//return reference to head element of the linked list.
}

void displayLinkedList(node *head)
{
     struct node *temp;

     if(head == NULL)
     {
        printf("LinkedList is empty.\n\n");
     }
     else
     {
        temp = head;
        printf("Displaying linked List.\n\n");
 
        while(temp != NULL)
        {
          cout<<temp->data<<"=====>";
          temp = temp->next;
        }

      printf("END\n\n");
     }
}

// Returns 1 if string formed by linked
// list is palindrome
int checkForPalindrome(node *sourcenode)
{
    // Append all nodes to form a string
     string str = "";

    while (sourcenode != NULL)
    {
       str.append(sourcenode->data);
       sourcenode = sourcenode->next;
    }

    // Check if the formed string is palindrome
    int length = str.length();

    // Match characters from beginning and
    // end.

    for (int i=0; i <=length; i++)
    {
      if (str[i] != str[length-i-1])
      {
        //It is not Palindrome
        return 0;
      }
    }

    //It is a Palindrome.Reverse of string is equal to actual string.

    return 1;
}

//Input Program to pass "Top Spot"
//If we combine the all the characters in the String:topspot
//Main program
int main()
{
    int n, position;

    /* It will create Linked List with given N nodes*/
    printf("Enter the total number of nodes to create: \n\n");
    scanf("%d", &n);

    node* head=GenerateLinkedList(n);//Head of the linked list is stored in "head".

    //Display created linked list.
    displayLinkedList(head);

    //Pass it to Actual method,which will do the actual work of checking.
    if(checkForPalindrome(head))
    {
       printf("Given String is Palindrome,Because Reverse of the String is Equal to Original String. \n\n");
    }
    else
    {
      printf("Given String is not Palindrome \n\n");
    }
    return 0;
}

 

 complete Program to check whether given linkedlist with string forms a palindrome Output


                            complete Program to check whether given linkedlist with string forms a palindrome Output

I have compiled and Executed above Program .Attached here for the reference.If any doubts,leave the comment here,i am happy to answer your queries.

Happy Coding 🙂

The following two tabs change content below.

SRINIVAS DARIPELLI

Myself SRINIVAS DARIPELLI. I have 15+ Years of Experience in Programming worked on multiple technologies.Apart from it,I am a blogger, writer, editor, artist and dad 🙂 .I believe in reality.I love to share the Helpful things around the Technology. Feel free to connect with me

Leave a Reply