Check if linked list is a palindrome
Check if a linked list containing integer data is a palindrome. Eg: HEAD-->1-->2-->3-->3-->2-->1-->NULL is a palindrome.
/*
* PalindromeCheck.cpp
*
* Created on: Apr 19, 2012
* Author: Kiran Hegde
*/
#include <iostream>
#include <stack>
using namespace std;
struct Node {
int data;
Node *next;
};
/**
* Generate a linked list of length "size" containing random numbers from 1 to 10
*/
Node *createPalindrome(int size) {
Node *head = NULL;
for (int i = 1; i <= size; i++) {
Node *node = new Node;
if (i <= size/2){
node->data = i;
}
else {
node->data = size-i+1;
}
node->next = head;
head = node;
}
return head;
}
void deleteLinkedList(Node *head) {
while (head != NULL) {
Node *temp = head;
head = head->next;
delete temp;
}
}
void printLinkedList(Node *head) {
Node *curr = head;
while (curr != NULL) {
cout << curr->data << "-->";
curr = curr->next;
}
cout << "EMPTY" << endl;
}
/**
* Values in the first half of the list list are stored into a stack. Afterwards as the
* linked list pointer traverses the second half of the list, values are popped off the
* stack and compared. If they are different, then not a palindrome
*/
bool isPalindrome(Node *head) {
Node *fast = head;
Node *slow = head;
stack<int> myStack;
while (fast != NULL && fast->next != NULL) {
myStack.push(slow->data);
fast = fast->next->next;
slow = slow->next;
}
//If linked list is of odd size, move slow by one
if (fast != NULL) {
slow = slow->next;
}
bool retFlag = true; // retFlag is true if palindrome
while (slow != NULL) {
//pop value from stack and compare with slow pointer
int value = myStack.top();
myStack.pop();
if (slow->data != value) {
retFlag = false;
break;
}
slow = slow->next;
}
return retFlag;
}
/**
* Test the function
*/
int main() {
Node *head = createPalindrome(11);
cout << "Original List: " << endl;
printLinkedList(head);
cout << "List is a palindrome: " << (isPalindrome(head)?"Yes":"No") << endl;
head->next->next->data = 8;
cout << "New List: " << endl;
printLinkedList(head);
cout << "List is a palindrome: " << (isPalindrome(head)?"Yes":"No") << endl;
deleteLinkedList(head);
return 0;
}