Check if a linked list is a palindrome: Non-recursive version

Write a program to check if a linked list is a palindrome without using recursion.

The approach:-

1. Solution for this problem is to reach midway of the list and start comparing both sides as we move from midway to end of list.


2. The first half of the list node pointers are pushed to stack (implemented as array here).

The solution:-

#include <iostream>

using namespace std;

// General list node
class Node {
    public:
        Node() { mData = -1; mNext = NULL; }
        ~Node() {}
        int data() { return mData; }
        void setData(int data) { mData = data; }
        Node* next() { return mNext; }
        void setNext(Node* next) { mNext = next; }
    private:
        int mData;
        Node* mNext;
};

// General list class
class List {
    public:
        List() { mHead = NULL; mCount = 0; }
        ~List() {}
        Node* head() { return mHead; }
        void setHead(Node* head) { mHead = head; }

        void append(int data) {
            Node* tmp = new Node();
            tmp->setData(data);
            if ( mHead == NULL )
                    mHead = tmp;
            else {
                Node* ptr = mHead;
                while ( ptr->next() != NULL ) {
                        ptr = ptr->next();
                }
                ptr->setNext(tmp);
            }
        }

        void prepend(int data) {
            Node* tmp = new Node();
            tmp->setData(data);
            tmp->setNext(mHead);
            mHead = tmp;
        }

        void print() {
            Node* ptr = mHead;
            while ( ptr != NULL ) {
                cout <data() <next();
            }
            cout <next();
            }
            return count;
        }

    private:
        Node* mHead;
        int mCount;
};

bool isListPalindrome(List* l)
{
    int size = l->size();
    int len = size/2;
    Node **stackArray = new Node*[len];
    Node* node = l->head();
    int i = 0;
    while(len-- > 0) {
        stackArray[i++] = node;
        node = node->next();
    }
    i--;
    if (size & 0x1)
        node = node->next();

    while (node)
    {
        if (((Node *)stackArray[i])->data() != node->data()) {
            delete [] stackArray;
            return false;
        }
        node = node->next();
        i--;
    }

    delete [] stackArray;
    return true;
}

int main() {
    List* l = new List();
    l->append(100);
    l->append(200);
    l->append(300);
    l->append(400);
    l->append(300);
    l->append(200);
    l->append(100);
    l->print();

    bool stat = isListPalindrome(l);
    if ( stat ) {
        cout << "Linked list is palindrome" << endl;
    }
    else {
        cout << "Linked list is not a palindrome" << endl;
    }

    delete l;
    return 0;
}

Output:-

100 200 300 400 300 200 100
Linked list is palindrome