#include<iostream>
using namespace std;

struct Node 
{
    int data;
    Node* next;
};

// Function to create a new node for a linked list
Node* create_node(int value) 
{
    Node* newNode = new Node;
    newNode->data = value;
    newNode->next = nullptr;
    return newNode;
}

// Function to reverse a linked list
Node* reverse_list(Node* head)
{
    Node* prev = nullptr;
    Node* current = head;
    Node* nextNode = nullptr;

    while (current != nullptr) 
    {
        nextNode = current->next; // Store the next node
        current->next = prev; // Reverse the link

        // Move pointers to the next positions
        prev = current;
        current = nextNode;
    }

    return prev; // The new head of the reversed list
}

// Function to insert a new node into a linked list
void insert_into_list(Node* &head, int value, int position)
{
    if (position == 0) 
    {
        Node* newNode = create_node(value);
        newNode->next = head;
        head = newNode;
        return;
    }
    else if (position == -1)
    {
        Node* newNode = create_node(value);
        if (head == nullptr)
            head = newNode;
        else 
        {
            Node* current = head;
            while (current->next != nullptr)
                current = current->next;
            current->next = newNode;
        }
        return;
    }

    Node* newNode = create_node(value);
    Node* current = head;
    for (int i = 1; i < position && current != nullptr; ++i)
        current = current->next;

    if (current != nullptr) 
    {
        newNode->next = current->next;
        current->next = newNode;
    }
}

// Function to display the linked list
void display_list(Node* head) 
{
    Node* current = head;
    while (current != nullptr) 
    {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main() 
{
    Node* head = nullptr; // Initializing an empty linked list
    
    // Inserting elements into the linked list
    insert_into_list(head, 5, 0);
    insert_into_list(head, 10, 0);
    insert_into_list(head, 15, -1);
    insert_into_list(head, 20, 1);
    
    head = reverse_list(head);
    display_list(head);
    
}