Thursday, July 12, 2012

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() {}
        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 << 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:
        Node* mHead;
        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();

    Node* n1 = l->head();
    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
Linked list is palindrome

7 comments :

  1. Is,
    delete l;
    Freeing all nodes in linked list ? If yes, please explain how ?

    ReplyDelete
  2. can someone explain the code? how n2 is traversing in reverse?

    ReplyDelete
  3. here there is a problem.
    Example: madam
    m==m. a===a, d==d then what is the use of checking again a==a ,m==m this check are of no use.
    Can we avoid this extra check.
    Thanks

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. You could use a stack. First count length of list then push half the items in order onto the stack, then pop off the stack with the second half. It is an O(N) solution.

    ReplyDelete
    Replies
    1. pop off if the second half matches the item in stack

      Delete

Contact Form

Name

Email *

Message *

Back to Top