Implement a function in the following C++ code to check if a linked list is a pa
ID: 3861184 • Letter: I
Question
Implement a function in the following C++ code to check if a linked list is a palindrome.
#include <iostream>
using namespace std;
typedef struct linked_list{
int data;
struct linked_list *next;
}Linked_list;
int list_add(Linked_list **head, int d)
{
Linked_list *l = new Linked_list;
if(l == NULL) return 0;
Linked_list *t = *head;
l->data = d;
l->next = NULL;
if(*head == NULL){
*head = l;
return 1;
}
while(t->next != NULL){
t = t->next;
}
t->next = l;
return 1;
}
int list_remove_dup(Linked_list *head)
{
Linked_list *current;
Linked_list *previous;
linked_list *runner;
linked_list *tmp;
if(head == NULL) return 0;
if(head->next == NULL) return 1;
current = head->next;
previous = head;
while(current != NULL){
runner = head;
while(runner != current){
// remove node if equal
if(runner->data == current->data){
tmp = current;
current = current->next;
previous->next = current;
delete tmp;
break;
}
runner = runner->next;
}
if(runner == current){
current = current->next;
previous = previous->next;
}
}
}
int main(int argc, char* argv[])
{
Linked_list *head = NULL;
Linked_list *l;
list_add(&head, 1);
list_add(&head, 1);
list_add(&head, 2);
list_add(&head, 3);
list_add(&head, 9);
list_add(&head, 4);
list_add(&head, 1);
list_add(&head, 5);
cout << "before" << endl;
l = head;
while(l!=NULL){
cout << l->data << endl;
l = l->next;
}
list_remove_dup(head);
cout << "after remove dup " << endl;
l = head;
while(l!=NULL){
cout << l->data << endl;
l = l->next;
}
return 0;
}
Explanation / Answer
bool isPalindrome(Linked_list *head)
{
int count = 0;
Linked_list *temp = head;
if(temp != null)
{
count++;
temp = temp->next;
}
return isPalindromeUtil(head,count);
}
bool isPalindromeUtil(Linked_list *head,int count){
int i= 0,j;
struct Linked_list *start;
struct Linked_list *end;
while (i != count / 2)
{
start = head;
end = head;
for (j = 0; j < i; j++)
{
start = start->next;
}
for (j = 0; j < count - (i + 1); j++)
{
end = end->next;
}
if (start->data != end->data)
{
return false;
}
else
{
i++;
}
}
return true;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.