Norway


#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

// Structure to store a

struct Node

{

    string data;

    Node* next;

 

    // Constructor

    Node(string str)

    {

        this->data = str;

        this->next = nullptr;

    }

};

 

// Function to print a linked list

void printList(Node* node)

{

    while (node)

    {

        cout << node->data << ” -> “;

        node = node->next;

    }

 

    cout << “null”;

}

 

// Function to reverse a string

string reverse(string const &s)

{

    string rev = “”;

    for_each(s.rbegin(), s.rend(), [&rev] (char const &c) {

                rev = rev.append(1, c);

            });

 

    return rev;

}

 

// Construct string s1 and s2 out of given linked list with consecutive

// elements of the list in forward and backward direction respectively

void construct(Node* &head, string &s1, string &s2)

{

    // Base case

    if (head == nullptr)

        return;

 

    s1 += head->data;

    construct(head->next, s1, s2);

    s2 += reverse(head->data);

}

 

// Function to if a given linked list of is

bool isPalindromic(Node *head)

{

    // construct string s1 with consecutive elements of the linked list

    // construct string s2 by reversing consecutive elements of the linked list

    // starting from the end

    string s1, s2;

    construct(head, s1, s2);

 

    // check if linked list is palindromic

    return s1 == s2;

}

 

// main function

int main()

{

    Node *head = new Node(“AA”);

    head->next = new Node(“XYZ”);

    head->next->next = new Node(“CD”);

    head->next->next->next = new Node(“C”);

    head->next->next->next->next = new Node(“ZYX”);

    head->next->next->next->next->next = new Node(“AA”);

 

    cout << “Linked List “;

    printList(head);

 

    if (isPalindromic(head))

        cout << ” is a palindrome.”;

    else

        cout << ” is not a palindrome.”;

 

    return 0;

}



Source link

LEAVE A REPLY

Please enter your comment!
Please enter your name here