﻿ Check if a linked list is a palindrome ~ Programming Tutorials by SourceTricks
Thursday, July 12, 2012

## Check if a linked list is a palindrome

### Write a program to check if a linked list is a palindrome

The approach:-
1. Solution for this problem is recursion with a reference to head node of the list.

2. Whenever the recursive function returns compare the node values and move the reference to the next node.

#### C++ program to check if a linked list is a palindrome

#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() {}

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

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

void print() {
while ( ptr != NULL ) {
cout << ptr->data() << " ";
ptr = ptr->next();
}
cout << endl;
}

bool isPalindrome(Node*& n1, Node* n2) {
if ( ! n2 )
return true;

if ( ! isPalindrome(n1, n2->next()) )
return false;

bool flag = ( n1->data() == n2->data() );

n1 = n1->next();

return flag;
}

private:
int mCount;
};

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 = l->isPalindrome(n1, n1);
if ( stat ) {
cout << "Linked list is palindrome" << endl;
}
else {
cout << "Linked list is not a palindrome" << endl;
}

delete l;
}

Output:-
100 200 300 400 300 200 100