// c++ program to create a linked list insert element at head, at tail and delete element from
// tail, head and specific key
#include <iostream>
using namespace std;
struct Node
{
public:
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
void insertAtHead(Node *&head, int data)
{
    Node *NewNode = new Node(data);
    NewNode->next = head;
    head = NewNode;
}
void insertAtTail(Node *&head, int data)
{
    Node *NewNode = new Node(data);
    if (head == NULL)
    {
        NewNode->next = head;
        head = NewNode;
        return;
    }
    Node *temp = head;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = NewNode;

    cout << "the value of temp next is " << temp->data << endl;
}
void insertAtKey(Node *&head, int key, int data)
{
    Node *NewNode = new Node(data);
    if (head->data == key)
    {

        NewNode->next = head->next;
        head->next = NewNode;
        return;
    }
    Node *temp = head;
    while (temp->data != key)
    {
        temp = temp->next;
        if (temp == NULL)
            return;
    }
    NewNode->next = temp->next;
    temp->next = NewNode;
}
void print(Node *&head)
{
    if (head == NULL)
    {
        cout << head->data << " ->  ";
    }
    Node *temp = head;
    while (temp != NULL)
    {
        /* code */
        cout << temp->data << " -> ";
        temp = temp->next;
    }
}

void deleteNode(Node *&head, int key)
{
    if (head == NULL)
        return;

    if (head->data == key)
    {
        Node *temp = head;
        head = head->next;
        delete temp;
    }
    deleteNode(head->next, key);
}
// recursive approach to reverse the linked list
Node *Reverse(Node *&head)
{
    if (head == NULL || head->next == NULL)
        return head;
    Node *NewHead = Reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return NewHead;
}
//this function reverse the k nodes in linked list
Node*Reversek(Node*&head,int k){
//first we have to make three node pointers

Node *prevPtr = NULL;//the prev ptr points to Null
Node *currPtr = head;//the next ptr should points toward the prev ptr because we have to reverse 
//the nodes this is possible if we point the next node towards the prev node
Node *nextptr=NULL;//we will assign the value to nextptr in the loop 
int count = 0;
while(currPtr!=NULL && count<k)
{
    nextptr = currPtr->next;
    currPtr->next = prevPtr;
    prevPtr = currPtr;
    currPtr = nextptr;
    count++;
}
if(nextptr!=NULL){
head->next = Reversek(nextptr, k);
}
return prevPtr;
}
int main()
{
    Node *head = NULL;
    cout << "insert At head" << endl;
    insertAtHead(head, 3);
    insertAtHead(head, 2);
    print(head);
    cout << endl;
    cout << "Insert at Tail " << endl;
    insertAtTail(head, 4);
    insertAtTail(head, 5);
    insertAtTail(head, 6);
    insertAtTail(head, 10);
    insertAtTail(head, 9);
    insertAtKey(head, 10, 45);
    print(head);

    deleteNode(head, 2);
    cout << "deleting the head" << endl;
    print(head);
    cout << endl;
    cout << "reversing the linked list " << endl;
    Node *NewHead = Reverse(head);
    print(NewHead);
    cout << endl;
    cout << "reversing the k nodes in linked list " << endl;
    Node *NewRev = Reversek(NewHead,2);
    print(NewRev);
}