CHECK ITS PELINDROME USING LINK LIST

Q.) CHECK WHETHER A NUMBER OR STRING IS PELINDROME OR NOT 
SOLUTION)---
----***CHECK WHETHER STRING /NUMBER IS PELINDROME OR NOT***----



#include
#include
#include
int main()
{
    struct node
    {
        char data;
        struct node *prev;
        struct node *next;
    }*head;
    head=NULL;
    struct node *temp,*end,*temp1;
    char str[1000];
    int n,num,i;
    scanf("%s",str);
    num=strlen(str);
    for(i=0;i
    {
        if(head==NULL)
        {
            head=malloc(sizeof(struct node));
            head->data=str[i];
            temp=head;
            temp->prev=NULL;
        }
        else
        {
            temp->next=malloc(sizeof(struct node));
            temp->next->prev=temp;
            temp->next->data=str[i];
            temp=temp->next;
        }
    }
    temp->next=NULL;
    end=temp;
    temp1=head;
    temp=end;
    int flag=1;
    if(num%2==0)
    {
        for(i=1;i<=num/2;i++)
        {
            if(temp1->data!=temp->data)
            {
                 flag=0;
            }
            temp1=temp1->next;
            temp=temp->prev;
        }
    }
    else
    {
        for(i=1;i
        {
            if(temp1->data!=temp->data)
            {
                 flag=0;
            }
            temp1=temp1->next;
            temp=temp->prev;
        }
    }
    if(flag==0)
    printf("it is not a pelindrome");
    else
    printf("it is a pelindrome");
    return 0;
}

SOLUTION USING STACK BY ARNAB DUTTA --

check_LinkedList_Is_Palindrome(LList head){

Stack myStack = new Stack(); //c1 = O(1)

//Take 2 LList pointers: slowPtr1 & fastPtr2
LList slowPtr1 = fastPtr2 = head; //c2 = O(2)

//keep running this loop until fastPtr2 becomes the TAIL
while( fastPtr2 != NULL && fastPtr2.next!=NULL) //O(n/2) as note fastPtr2 increases in double speed
{ 
//Store the slowPtr1 value to Stack 
myStack.push(ptr1.value);
//Advance the a) slowPtr1 by 1 node AND b) fastPtr2 by 2 nodes 
slowPtr1 = slowPtr1.next;
fastPtr2=fastPtr2.next.next; 
}

/**Note: At this point after the above while loop has ended, a) fastPtr2 reaches TAIL and b) slowPtr1 reached Middle of LList**/

//Now from here(ie. slowPtr1 at MIDDLE) till slowPtr1 reaches TAIL,
//Pop from the Stack() and match against slowPtr1.value [ Unless different found, the palindrome property holds fine!
If found different, its not palindrome]
while(slowPtr1!=NULL && slowPtr1.next != NULL){ //O(n/2) as note slowPtr1 starts here from at MIDDLE
slowPtr1 = slowPtr1.next;
if(slowPtr1.value != myStack.pop().value){
sout("Not a palindrone");
break;
}
}
/**Note: At this point after the above while loop has ended( if not by 'break' ) then **/
if(slowPtr1==NULL || slowPtr1.next == NULL) {
sout("Its Palindrome");
}
}


Time Complexity: c1 + c2 + O(n/2) + O(n/2) ~ O(n)
Space Complexity : O(n/2) which is < O(n) for the Stack