#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

void appendList(Node*& head, Node* list) {
    if (head == nullptr) {
        head = list;
    }
    else {
        Node* curr = head;
        while (curr->next != nullptr) {
            curr = curr->next;
        }
        curr->next = list;
    }
}

void flipList(Node*& head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }

    Node* rest = head->next;
    flipList(rest);
    head->next->next = head;
    head->next = nullptr;
    head = rest;
}

void printList(Node* head) {
    Node* curr = head;
    while (curr != nullptr) {
        std::cout << curr->data << " ";
        curr = curr->next;
    }
    std::cout << std::endl;
}

void moveNodesToEnd(Node** head_ref, int n) {
    if (*head_ref == nullptr || n == 0) {
        return;
    }

    Node* current = *head_ref;

    // Find the nth node
    for (int i = 1; i < n && current != nullptr; i++) {
        current = current->next;
    }

    // If nth node is not present, return
    if (current == nullptr) {
        return;
    }

    // Save the nth node
    Node* nthNode = current;

    // Find the last node of the list
    while (current->next != nullptr) {
        current = current->next;
    }

    // Connect the last node to the head node
    current->next = *head_ref;

    // Change head to (n+1)th node
    *head_ref = nthNode->next;

    // Connect the last node to nullptr
    nthNode->next = nullptr;


}

int countNodesBefore(Node* head, int nodeNum) {
    int count = 0;
    Node* current = head;

    // Проходим по всем узлам списка
    while (current != nullptr) {
        // Если нашли нужный узел, возвращаем количество пройденных узлов
        if (count == nodeNum) {
            return count;
        }

        // Иначе продолжаем двигаться по списку и увеличиваем счетчик
        current = current->next;
        count++;
    }

    // Если узел с указанным номером не найден, возвращаем -1
    return -1;
}


void flip_end_elements(Node*& head, int pos) {
    if (!head || !head->next) {
        return;  // Nothing to flip
    }

    // Find the position node
    Node* pos_node = head;
    for (int i = 1; i < pos && pos_node; i++) {
        pos_node = pos_node->next;
    }
    if (!pos_node) {
        return;  // Invalid position
    }

    // Reverse the nodes after the position node
    Node* prev = nullptr;
    Node* curr = pos_node->next;
    while (curr) {
        Node* temp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = temp;
    }

    // Connect the reversed nodes back to the list
    pos_node->next = prev;
}


int main() {
    Node* head = nullptr;
    int n;
    std::cout << "Enter the number of nodes: ";
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        int value;
        std::cout << "Enter the value of node " << i << ": ";
        std::cin >> value;
        std::cout<<"\n";
        appendList(head, new Node(value));
    }

    std::cout << "Original list: ";
    printList(head);

    int value;
    std::cout << "Enter the value to start the reformatted list: ";
    std::cin >> value;

    int nodes = countNodesBefore(head,value);

    moveNodesToEnd(&head, nodes);

    std::cout << "Reformatted list: ";
    printList(head);
    std::cout<<"\n";

    flip_end_elements(head,value);
    printList(head);

    exit(0);

    return 0;
}