Palindrome LinkedList

Question

Method:

1. Traverse the given list from head to tail and push every visited node to stack.

2. Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node.

3. If all nodes matched, then return true, else false.

Edit: The program compiles without an error but stops working during run time

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

struct Node
{
int data;
struct Node *next;
};
struct Stack
{
unsigned capacity;
int top;
int * array;
};
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack=(struct Stack*)malloc(sizeof(struct Stack));
stack->capacity=capacity;
stack->top=-1;
stack->array=(int *)malloc(sizeof(int)*stack->capacity);
return stack;
}
int isFull(struct Stack* stack)
{   return stack->top == stack->capacity - 1; }

// Stack 
int isEmpty(struct Stack* stack)
{   return stack->top == -1;  }

// stack.
void push(struct Stack* stack, int item)
{
if (isFull(stack))
    return;
stack->array[++stack->top] = item;
printf("%d pushed to stack\n", item);
}

// stack.  
int pop(struct Stack* stack)
{
if (isEmpty(stack))
    return INT_MIN;
return stack->array[stack->top--];
}

//  stack
int peek(struct Stack* stack)
{
if (isEmpty(stack))
    return INT_MIN;
return stack->array[stack->top];
}
// linkedlist
void insert(struct Node** head_ref, int new_data)
{

struct Node* new_node =
        (struct Node*) malloc(sizeof(struct Node));

new_node->data  = new_data;


new_node->next = (*head_ref);


(*head_ref)    = new_node;
}

bool compare(struct Stack* stack,struct Node* head)
{
struct Node* temp,* curr=head;
while(temp)
{
    push(stack,temp->data);
    temp=temp->next;
}
while(curr)
{
    if(pop(stack)==curr->data)
    {
       curr=curr->next;
    }
    else
    exit(0);
}
return true;

} 
// Driver program to test above functions
int main()
{
struct Stack* stack = createStack(100);
struct Node* head=NULL;
insert(&head,1);
insert(&head,2);
insert(&head,1);
printf("%s",compare(stack,head));

return 0;
}

Answer 1

Function compare has at least two errors. The first one is that it uses uninitialized pointer temp

bool compare(struct Stack* stack,struct Node* head)
{
struct Node* temp,* curr=head;
while(temp) // <= temp is not initialized
{

The second one is that the function never returns false though according to the assignment it has to return false if values in the list and in the stack do not match. Instead of returning false you call function exit

else
exit(0);

I would write the function the following way

bool compare(struct Stack *stack, struct Node *head )
{
    struct Node *current = head;

    for ( ; current != NULL && !isFull( stack ); current = current->next )
    {
        push( stack, current->data );
    }

    current = head;

    while ( current != NULL && !isEmpty( stack ) && pop( stack ) == current->data )
    {
        current = current->next;
    } 

    return current == NULL && isEmpty( stack );
} 

It is the only correct function implementation among presented here function implementations in other answers.:)

As C does not have type bool then that you could use name bool in a program written in C you have to include header <stdbool.h> or define this name yourself as a typedef either of _Bool (if your compiler supports this type) or of int.

You could declare the return type of the function as int if you do not want to include header <stdbool.h>. For example

int compare(struct Stack *stack, struct Node *head );

Take into account that you need to write also functions that will free all allocated memory for the list and the stack.

For example you could free memory allocated for the stack the following way

void freeStack( struct Stack **stack )
{
    if ( *stack != NULL ) free( ( *stack )->array );
    free( *stack );

    *stack = NULL;
}

The same way you could free the memory allocated for the list

void freeList( struct Node **head )
{
    if ( *head != NULL )
    {
        Node *current = ( *head )->next;

        while ( current != NULL )
        {
            Node *temp = current;
            current = current->next;
            free( temp );
        }
    }

    free( *head );

    *head = NULL;
}  

Answer 2

You've got an uninitialized local variable temp:

bool compare(struct Stack* stack,struct Node* head)
{
    struct Node* temp,* curr=head;
    while(temp)  // NOT INITIALIZED
    {
        push(stack,temp->data);
        temp=temp->next;
    }
    while(curr)
    {
        if(pop(stack)==curr->data)
        {
            curr=curr->next;
        }
        else
            exit(0);
    }
    return true;
} 

You need to fix that first; I think the following should work:

bool compare(struct Stack* stack,struct Node* head)
{
    struct Node  *curr;

    for (curr = head; curr != NULL; curr = curr->next)
    {
        push(stack, curr->data);
    }

    for (curr = head; curr != NULL; curr = curr->next)
    {
        if (pop(stack) != curr->data)
            return false;
    }
    return true;
} 

Next, you're printing a boolean result with "%s", which is for strings. You need to do something like:

    c=compare(stack,head);
    printf("%d\n", c);

or alternatively

    printf("%s\n", c ? "true" : "false");

At this point, it no longer crashes for me, and works for a couple simple test cases. You might think about how to handle the case of overflowing the stack, and also consider formatting your code to make it more readable.

Answer 3

struct Node* temp;

temp is not initialized in

bool compare(struct Stack* stack,struct Node* head)

struct Node* temp,* curr=head;

is not

struct struct Node* temp=head,* curr=head;

Using uninitialized variables lead to undefined behavior.

Answer 4

bool compare(struct Stack* stack,struct Node* head) {
    struct Node* temp=head;//<- Needs initialising. It wasn't.
    struct Node* curr=head;
    while(temp) {
        push(stack,temp->data);
        temp=temp->next;
    }
    while(curr) {
        if(pop(stack)==curr->data) {
           curr=curr->next;
        } else {
            //exit(0); <--Some mistake surely!
            return false; //Slightly less drastic!
        }
    }
    return true;
}

It's slightly a matter of taste but I find long series of variable declarations to be difficult to read and hence error-prone.

You only really need one local variable - but your compiler probably optimizes that away.

exit(0) will abruptly end the program. Most likely indicates 'success' (the exit of 0).

You should return false;.

PS: Credit for using #include <stdbool.h>.