### 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;`
`}`