StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Thursday, July 12, 2012

Check if a linked list is a palindrome

 July 12, 2012     Programming problems in CPP     No comments   

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
Email ThisBlogThis!Share to XShare to Facebook

Related Posts:

  • Find the first occurrence of unique character in a stringWrite a program to find the first occurrence of a unique character in a string For example, given a string: "aBcBcaAbBaAdAc", b and d are unique occu… Read More
  • Longest common substring problemWrite a program to find the longest common sub-string of two given strings The approach:- Key to the LCS problem is to generate a LCS matrix based … Read More
  • Compress a stringWrite a program to compress a string. If input is "aabbb" expected output is "a2b3" The approach:- Have 2 pointers read and write to the input st… Read More
  • Replace spaces in a string with "%20".Write a program to replace spaces in a string with %20 The approach: Typically in this problem we are expected to use optimal memory. This requires … Read More
  • Find if two strings are anagramsWrite a program to find if two strings are anagrams Anagram - Wikipedia An anagram is a type of word play, the result of rearranging the letters of a… Read More
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Python FastAPI file upload and download
    In this article, we will look at an example of how to implement a file upload and download API in a Python FastAPI microservice. Example bel...
  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Accessing the Kubernetes API
    In this article, we will explore the steps required to access the Kubernetes API and overcome common challenges. All operations and communic...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Scheduling jobs in Python
    When developing applications and microservices we run into scenarios where there is a need to run scheduled tasks. Examples include performi...
  • Using Tekton to deploy KNative services
    Tekton is a popular open-source framework for building continuous delivery pipelines. Tekton provides a declarative way to define pipelines ...

Copyright © 2025 StackStalk