Question

you will be implementing two functions for the LinkedList class. The function that you are implementing is called reverse and isPalindrome. The isPalindrome function should determine if the linked list is a palindrome or not and the reverse function should reverse the linked list.

When you are finished with the implementation, try to use valgrind to see if there are any other errors or memory leaks to deal with. valgrind ./lab7 or make val

1. Expected Output

This is an example of what the output should look like. Note that the program must compile without any warnings or memory leaks.

==2353315== Memcheck, a memory error detector

==2353315== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.

==2353315== Using Valgrind-3.16.0 and LibVEX; rerun with -h for copyright info

==2353315== Command: ./lab7

==2353315==

The word: tenet is a palindrome.

The word: LOLO is not a palindrome.

The word: Zendaya is not a palindrome.

The word: kayak is a palindrome.

The word: step on no pets is a palindrome.

The word: I did did I is a palindrome.

The word: CMSC 202 is not a palindrome.

The word: wasitacatisaw is a palindrome.

==2353315==

==2353315== HEAP SUMMARY:

==2353315==     in use at exit: 0 bytes in 0 blocks

==2353315==   total heap usage: 158 allocs, 158 frees, 76,512 bytes allocated

==2353315==

==2353315== All heap blocks were freed -- no leaks are possible

==2353315==

==2353315== For lists of detected and suppressed errors, rerun with: -s

==2353315== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Answer 1

class LinkedList

{

class Node {

public:

int data;

Node* next;

Node(int x){

this->data=x;this->next=NULL;}

};

Node* reverse(Node*head)
{
Node* c= head;
Node* s= NULL;
Node* n=NULL;
while(c!= NULL)
{
s=c;
c=c->next;
s->next=n;
n=s;
}
return s;
}

//this method extracts the second half of list and reverses it.Then we compare first half with second half.

bool isPalindrome(Node *head)
{
if(!head || !head->next)
return true;
Node *slow=head,*fast=head;
Node *pre=NULL;
while(slow && fast && fast->next)
{
pre=slow;
slow=slow->next;
fast=fast->next->next;
}
if(fast==NULL)
{
pre->next=NULL;
Node *x=reverse(slow);
}
else
{
pre=slow->next;
slow->next=NULL;
Node *x=reverse(pre);
}
Node *temp=head;
while(temp && x)
{
if(temp->data!=x->data)
return false;
temp=temp->next;
x=x->next;
}
return true;
}

return s;

}

};

AS THERE ARE NO MEMORY ALLOCATIONS EXCEPT POINTERS,THERE ARE NO MEMORY LEAKS!!