fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. template<class T>
  5. class Double;
  6.  
  7. template <class T>
  8. class DoubleNode {
  9.     friend class Double<T>;
  10. private:
  11.     T data;
  12.     DoubleNode<T> *left, *right;
  13. };
  14.  
  15. template <class T>
  16. class Double {
  17. public:
  18.     Double() { LeftEnd = RightEnd = nullptr; };
  19.     ~Double();
  20.     int Length() const;
  21.     bool CanFormPalindrome();
  22.     Double<T>& Insert(int k, const T& x);
  23.     void Output(std::ostream& out) const;
  24.     void ConstructFromString(const string& S); // New method for constructing from string
  25. private:
  26.     DoubleNode<T> *LeftEnd, *RightEnd;
  27. };
  28.  
  29. template <class T>
  30. Double<T>::~Double() {
  31.     while (LeftEnd != nullptr) {
  32.         DoubleNode<T>* temp = LeftEnd;
  33.         LeftEnd = LeftEnd->right;
  34.         delete temp;
  35.     }
  36. }
  37.  
  38. template <class T>
  39. int Double<T>::Length() const {
  40.     int len = 0;
  41.     DoubleNode<T>* current = LeftEnd;
  42.     while (current != nullptr) {
  43.         len++;
  44.         current = current->right;
  45.     }
  46.     return len;
  47. }
  48.  
  49. template <class T>
  50. bool Double<T>::CanFormPalindrome() {
  51.     int frequencies[128] = {0}; // Assuming ASCII characters
  52.  
  53.     // Traversing the doubly linked list to count the frequency of each character
  54.     DoubleNode<T>* current = LeftEnd;
  55.     while (current != nullptr) {
  56.         frequencies[current->data]++;
  57.         current = current->right;
  58.     }
  59.  
  60.     int oddCount = 0;
  61.  
  62.     // Counting the number of characters with odd frequencies
  63.     for (int i = 0; i < 128; i++) {
  64.         if (frequencies[i] % 2 != 0) {
  65.             oddCount++;
  66.             if (oddCount > 1) {
  67.                 return false;       // If the count of characters with odd frequencies is greater than one, palindrome cannot be formed
  68.             }
  69.         }
  70.     }
  71.  
  72.     // If the count of characters with odd frequencies is less than equal to one, palindrome can be formed
  73.     return true;
  74. }
  75.  
  76. template <class T>
  77. Double<T>& Double<T>::Insert(int k, const T& x) {
  78.     if (k < 1 || k > Length() + 1){
  79.         cout << "Invalid position";
  80.         return *this;
  81.     }
  82.  
  83.     DoubleNode<T>* newNode = new DoubleNode<T>;
  84.     newNode->data = x;
  85.  
  86.     if (k == 1) { // Inserting at the beginning
  87.         newNode->left = nullptr;
  88.         newNode->right = LeftEnd;
  89.         if (LeftEnd != nullptr)
  90.             LeftEnd->left = newNode;
  91.         LeftEnd = newNode;
  92.         if (RightEnd == nullptr)
  93.             RightEnd = LeftEnd;
  94.     } else if (k == Length() + 1) { // Inserting at the end
  95.         newNode->right = nullptr;
  96.         newNode->left = RightEnd;
  97.         RightEnd->right = newNode;
  98.         RightEnd = newNode;
  99.     } else { // Inserting in the middle
  100.         DoubleNode<T>* current = LeftEnd;
  101.         for (int i = 1; i < k; i++)
  102.             current = current->right;
  103.         newNode->right = current;
  104.         newNode->left = current->left;
  105.         current->left->right = newNode;
  106.         current->left = newNode;
  107.     }
  108.  
  109.     return *this;
  110. }
  111.  
  112. template <class T>
  113. void Double<T>::Output(std::ostream& out) const {
  114.     DoubleNode<T>* current = LeftEnd;
  115.     while (current != nullptr) {
  116.         out << current->data << " ";
  117.         current = current->right;
  118.     }
  119. }
  120.  
  121. // Function to construct DoublyLinkedList from a given string
  122. template <class T>
  123. void Double<T>::ConstructFromString(const string& S) {
  124.     for (char c : S) {
  125.         Insert(Length() + 1, c);
  126.     }
  127. }
  128.  
  129. int main() {
  130.     Double<char> dl;
  131.     string S = "carrace";
  132.     cout<<"Given string: "<<S<<endl;
  133.     cout<<"Constructing DLL from this string..."<<endl;
  134.     dl.ConstructFromString(S);
  135.     dl.Output(cout);
  136.     cout<<endl;
  137.  
  138.     if(dl.CanFormPalindrome()) {
  139.         cout << "The given doubly linked list can be rearranged to form a palindrome." << endl;
  140.     } else {
  141.         cout << "The given doubly linked list cannot be rearranged to form a palindrome." << endl;
  142.     }
  143.  
  144.     return 0;
  145. }
  146.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Given string: carrace
Constructing DLL from this string...
c a r r a c e 
The given doubly linked list can be rearranged to form a palindrome.
https://ideone.com/qbv7bx
language:
C++ 4.3.2 (gcc-4.3.2)
created:
29 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!