B Basak B Basak - 3 months ago 13
C Question

ProblemChecking If A Linked List Is Palindrome Or Not

I am trying the check if a link is palindrome or not using the following method:

1) Create and read the original linked list from user.
2) Traverse through the original linked list and using the stack implementation using linked list reverse the original linked list.
3) Initialize flag = 1. Traverse through both the linked lists and compare each node and break the loop and print "Not Palindrome" if any two node data doesn't match else print "Palindrome".

The Program Is Given Below:

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

int flag = 1;

struct node {
int data;
struct node *next;
}*start = NULL, *head = NULL;

void create() {
char ch;

do {
struct node *new_node, *prev;
new_node = (struct node*)malloc(sizeof(struct node));
printf("Please Enter The Data: ");
scanf("%d", &new_node->data);
new_node->next = NULL;
if(start == NULL) {
start = new_node;
} else {
prev->next = new_node;
}
prev = new_node;
printf("Do You Still Want To Insert(y/n)? ");
fflush(stdin);
scanf("%c", &ch);
}while(ch != 'n');
}

void reverse() {
struct node *current;
current = start;
while(current != NULL) {
struct node *new_node, *prev;
new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = current->data;
new_node->next = NULL;
if(head == NULL) {
head = new_node;
} else {
new_node->next = head;
head = new_node;
}
prev = new_node;
current = current->next;
}

}

int checkPal() {
struct node *current1, *current2;
current1 = start;
current2 = head;
while(current1 != NULL && current2 != NULL) {
if(current1->data != current2->data) {
flag = 0;
break;
}
current1 = current1->next;
current2 = current2->next;
}
if(flag = 1)
return 1;
else
return 0;
}

void display(struct node *list) {
while(list != NULL) {
printf("%d --> ", list->data);
list = list->next;
}
printf("NULL\n");
}

int main() {
create();
printf("The original linked list is: \n");
display(start);
reverse();
printf("The reversed linked list is: \n");
display(head);
if(checkPal()) {
printf("The Linked List Is Palindrome!\n");
} else {
printf("The Linked List Is Not Palindrome!\n");
}
}


However, I am always getting "The Linked List Is Palindrome!" even when it is not! What did I do wrong?

NOTE: To be done only with singly linked list.

Answer

So you have an error here

 if(flag = 1)
        return 1;
 else
        return 0;

This should be: if(flag == 1). With your code you are not checking for the value of flag but assigning 1 to flag But you can simplify this by simply returning flag:

return flag

Also, I did not scan through all your code, but I believe that flag does not need to be global as it it is only used in your checkPal() function, so you could declare it and initialise it there only.