if a linked list of strings forms a palindrome using map O(n)

if a linked list of strings forms a palindrome using map

time complexity O(n) 

Note:

This code will work fine for the odd length string and all the characters of the string should be different. All the condition will be updated soon.

The logic behind the checking the string is 

(i)insert all the char in the map with their corresponding index before the mid point.

(ii)check for all the char after mid point and compare the relation between their index

ex- if we have string abcba then

a will insert in the map with 1 index == a,1

b will insert in the map with 2 index== b,2

now we check for char after mid

for b we check if index of b already in the map is ==mid-1 is equal ? yes 3-1=2 

similarly for others ..

Little complex but when you understand it is fine

#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <map>

using namespace std;

struct node
{
    char data;
    struct node *next;
}*head;
void insert(char chr)
{
    struct node* temp;
    temp=(struct node *)malloc(sizeof(struct node));
    temp->data=chr;
    temp->next=NULL;
    if(head==NULL)
    {
        head=temp;
    }
    else
    {
        struct node* temp1=head;
        while(temp1->next!=NULL)
        {
            temp1=temp1->next;
        }
        temp1->next=temp;
    }

}

void display()
{
    struct node *temp2;
    temp2=head;
    while(temp2!=NULL)
    {
        printf("%c ",temp2->data);
        temp2=temp2->next;

    }

}
int length()
{
    struct node* temp=head;
    int count1=0;
    while(temp!=NULL)
    {
        temp=temp->next;
        count1=count1+1;
    }
    return count1;
}
void check_if_palindrome()
{
    int i;
    std::map<char,int> chrset;
    std::map<char,int>::iterator it;
    struct node* temp=head;
    int len=length();
    if(len%2!=0)
    {
    int mid=(len/2)+1;
    for(i=1;i<=mid-1;i++)
    {

        chrset.insert ( std::pair<char,int>(temp->data,i));
        temp=temp->next;
    }
    temp=temp->next;
    int val;
    bool amit=true;
    for(i=mid+1;i<=len;i++)
    {
        val=temp->data;
        //cout<<mid;
        //cout<<chrset.find(val)->second;
        if(chrset.find(val)->second!=mid-1)
        {
            printf("Not a palindrome\n");
            amit=false;
            break;
        }
        temp=temp->next;
        mid=mid-1;
    }
    if(amit==true)
    {
        printf("Yes this the palindrome");
    }


    }
}


int  main()
{
    int pos,i;
    char chr;
    struct node *n;
    head=NULL;
    while(1)
    {
    printf("\nList Operations\n");
    printf("===============\n");
    printf("1.Insert\n");
    printf("2.Display\n");
    printf("3. Check if Palindrome\n");
    printf("Enter your choice : ");
    if(scanf("%d",&i)<=0)
        {
        printf("Enter only an Integer\n");
        exit(0);
       }
    else
        {
        switch(i)
        {
        case 1:
            printf("Enter the char to insert : \n");
            scanf("%s",&chr);
            insert(chr);
                 break;
        case 2:     if(head==NULL)
                {
                printf("List is Empty\n");
                }
                else
                {
                printf("Element(s) in the list are : ");
                }
                display();
                break;
        case 3:
            printf("Checking the linked list is palindrome or not\n");
            check_if_palindrome();
            break;

        case 5:     return 0;



        default:    printf("Invalid option\n");
        }
        }

    }
    return 0;
}