#include <string>
#include <iostream>
#include <sstream>
using namespace std;

struct node {
    char data;
    node* next;
};

void outlist(node* L) {
    node* q1 = L;
    while (q1 != nullptr) {
        cout << q1->data;
        q1 = q1->next;
    }
    cout << "\n";
}

void crateList(node*& L) {
    cout << "Введите слова: \n";
    string data;
    getline(cin, data);

    node* lastNode = nullptr;
    node* tmp = nullptr;

    for (int i = 0; i < data.length(); i++) {
        lastNode = new node;
        lastNode->data = data[i];
        lastNode->next = nullptr;

        if (L == nullptr) {
            L = lastNode;
        }
        else {
            tmp = L;
            while (tmp->next != nullptr) {
                tmp = tmp->next;
            }
            tmp->next = lastNode;
        }
    }
}

void insertToStart(node*& L, int position) {
    node* q1 = L;
    node* nodeInPosition = nullptr;
    node* prevNodePtr = nullptr;
    int currentPosition = 1;

    while (q1->next != nullptr) {
        if ((currentPosition + 1) == position) {
            nodeInPosition = q1->next;
            prevNodePtr = q1;
        }

        q1 = q1->next;

        currentPosition++;
    }

    if (nodeInPosition != nullptr) {
        // элемент перед заданным в позиции становится последним  
        // qwe1 qwe2 qwe3
        prevNodePtr->next = nullptr;
        q1->next = nodeInPosition;
        node* temp = nodeInPosition->next;
        nodeInPosition->next = L;
        L = temp;
    }
}

// функция, которая находит последнее слово и переставляет его в начало списка.
void findLastStrAndInserToStart(node*& L) {
    node* q1 = L;
    int lastSpaceNodePos = 1;
    int i = 1;
    while (q1->next != nullptr) {
        if (q1->data == ' ') {
            lastSpaceNodePos = i;
        }
        q1 = q1->next;
        i++;
    }

    insertToStart(L, lastSpaceNodePos);
}

// функция, которая удаляет второе слово.
void deleteSecondWord(node* L) {
    while (L->next != nullptr) {
        if (L->data == ' ') {
            node* nodeWithSpace = L;
            node* tmp1 = L->next;
            while (tmp1->data != ' ') {
                node* tmp2 = tmp1;
                tmp1 = tmp1->next;
                delete tmp2;
            }
            nodeWithSpace->next = tmp1->next;
            delete tmp1;
            return;
        }
        L = L->next;
    }
}

// функция, которая заменяет k-ое слово на новое слово. Длина нового словаможет быть больше длины k-ого слова
void replaceWordInPosition(node*& L, int k) {
    node* q1 = L;
    int i = 1;
    while (q1->next != nullptr) {
        if (q1->data == ' ') {
            i++;
            if (i == k) {
                node* firstSpaceNode = q1;
                q1 = q1->next;
                while (q1 != nullptr) {
                    if (q1->data != ' ') {
                        node* tmp = q1;
                        q1 = q1->next;
                        delete tmp;
                    }
                    else {
                        break;
                    }
                }

                string data;
                cout << "Введите новое слово: \n";
                cin >> data;

                node* firstNode = nullptr;
                node* lastNode = nullptr;

                for (int i = 0; i < data.length(); i++) {
                    node* newNode = new node;
                    newNode->data = data[i];

                    if (firstNode == nullptr) {
                        firstNode = newNode;
                        lastNode = firstNode;
                    }
                    else {
                        lastNode->next = newNode;
                        lastNode = newNode;
                    }
                }
                firstSpaceNode->next = firstNode;
                lastNode->next = q1;
                return;
            }
        }
        q1 = q1->next;
    }
}

int main()
{
    setlocale(LC_ALL, "Russian");
    node* testNode = nullptr;
    cout << "Создание списка, используя вставку нового узла перед первым узлом\n";
    crateList(testNode);
    outlist(testNode);
    cout << "================================================================\n\n";
    findLastStrAndInserToStart(testNode);
    outlist(testNode);
    cout << "================================================================\n\n";
    deleteSecondWord(testNode);
    outlist(testNode);
    cout << "================================================================\n\n";
    replaceWordInPosition(testNode, 2);
    outlist(testNode);
    cout << "================================================================\n\n";
}