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

The approach:-

- 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.
- 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

## 0 comments:

## Post a Comment