#include <iostream>
#include <string>
using namespace std;
// Node structure for the double-linked list
struct Node {
string data;
Node* prev;
Node* next;
};
// Function to create a new node
Node* createNode(string data) {
Node* newNode = new Node();
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the end of the list
void insertNode(Node** head, string data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
}
else {
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}
// Function to display the list
void displayList(Node* head) {
Node* temp = head;
while (temp != NULL) {
cout << "Address: " << temp << endl;
cout << "Information Part: " << temp->data << endl;
cout << "Address Part: " << temp->next << endl;
cout << endl;
temp = temp->next;
}
}
void moveNodeToThirdPosition(Node** head) {
if (*head == nullptr || (*head)->next == nullptr || (*head)->next->next == nullptr) {
// Not enough nodes to perform the move
return;
}
Node* nodeToMove = *head;
*head = nodeToMove->next;
(*head)->prev = nullptr;
Node* nodeAtThirdPosition = (*head)->next;
nodeToMove->next = nodeAtThirdPosition;
nodeToMove->prev = nodeAtThirdPosition->prev;
nodeAtThirdPosition->prev->next = nodeToMove;
nodeAtThirdPosition->prev = nodeToMove;
}
Node* rewriteList(Node* head) {
Node* temp = head;
int uppercaseCount = 0;
Node* newHead = nullptr;
Node* newTail = nullptr;
// First loop: Write all uppercase letters in the new doubly linked list
while (temp != nullptr) {
if (isupper(temp->data[0])) {
Node* newNode = createNode(temp->data);
if (newHead == nullptr) {
newHead = newNode;
newTail = newNode;
}
else {
newTail->next = newNode;
newNode->prev = newTail;
newTail = newNode;
}
}
temp = temp->next;
}
temp = head;
// Second loop: Write all nodes before finding the second uppercase letter from the original list at the end of the new list
while (temp != nullptr && uppercaseCount < 2) {
if (!isupper(temp->data[0])) {
Node* newNode = createNode(temp->data);
if (newHead == nullptr) {
newHead = newNode;
newTail = newNode;
}
else {
newTail->next = newNode;
newNode->prev = newTail;
newTail = newNode;
}
}
else {
uppercaseCount++;
}
temp = temp->next;
}
return newHead;
}
int main() {
Node* listHead = NULL;
// Enter names letter by letter
string input;
cout << "Enter your surname, first name, and patronymic letter by letter (separated by spaces):" << endl;
cout << "Type 'done' to finish entering names." << endl;
while (true) {
cin >> input;
if (input == "done") {
break;
}
insertNode(&listHead, input);
}
cout << endl << "Original List:" << endl;
displayList(listHead);
cout << endl << "Converted List:" << endl;
Node* newHead = rewriteList(listHead);
displayList(newHead);
return 0;
}