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;
}
Comments