Untitled

#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;
}