Linked_List

#include<bits/stdc++.h>
using namespace std;

class node {
public:
	int data;
	node* next;
	node(int data)
	{
		this->data = data;
		next = NULL;
	}
};

void takeinput(node* &head)
{
	int data; cin >> data;
	node* temp = NULL;
	while (data != -1)
	{
		node* n1 = new node(data);
		if (head == NULL)
		{
			head = n1; temp = n1;
		}
		else {
			(temp->next) = n1;
			temp = (temp->next);
		}
		cin >> data;
	}
}

void printlist(node* head) {
	while (head->next != NULL) {
		cout << head->data << " ";
		head = head->next;
	}
	cout << head->data;
}

node* deletenafterm(node* &head, int n, int m)
{
	// iterate till m first
	int count = 0;
	node* temp = head;
	while (count != m) {
		count++;
		if (count == m) break;
		temp = temp->next;
	}
	node* dummy = temp->next;
	count = 0;
	while (count != n) {
		count++;
		dummy = dummy->next;
	}
	temp->next = dummy;
	return head;
}

void deletemiddle(node* &head) {
	//1 2 3 4 5-> 1 2 4 5
	//1 2 3 4-> 1 2 4
	node* fast = head;
	node* slow = head;
	node* prev = NULL;
	while (fast != NULL && fast->next != NULL) {
		prev = slow;
		slow = slow->next;
		fast = fast->next->next;
	}
	prev->next = slow->next;
}

void deletekthfromend(node* &head, int k)
{
//1 2 3 4 5 6 7 8 -1, k=4
	node* p1 = head;
	node* p2 = head;
	node* prev = NULL;
	int count = 0;
	while (count != k) {
		count++;
		p2 = p2->next;
	}
	while (p2) {
		prev = p1;
		p1 = p1->next;
		p2 = p2->next;
	}
	if (prev == NULL) {
		prev = head->next;
		head = prev;
	}
	else {
		prev->next = p1->next;
	}
}

node* removeelements(node* &head, int val) {
	//remove all elements in the linked list with value val without modification and retunr the
	//head of a linked list
	if (head == NULL) return NULL;
	while (head != NULL && head->data == val) {
		head = head->next;
	}
	node* temp = head;
	node* prev = NULL;
	while (temp != NULL) {
		if (temp->data != val) {
			prev = temp; temp = temp ->next; continue;
		} else {
			prev->next = temp->next;
			temp = temp->next;
		}
	}
	return head;
}


node* itreverse(node* head)
{
	node* dummy = NULL;
	while (head != NULL)
	{
		node* temp = head->next;
		head->next = dummy;
		dummy = head;
		head = temp;
	}
	head = dummy;
	return head;
}
node* recreverse(node* head)
{
	if (head == NULL || head->next == NULL) return head;

	node* newhead = recreverse(head->next);
	node* temp = head->next;
	head->next = NULL;
	temp->next = head;
	return newhead;
}

node* cycle(node* & head)
{
	node* fast = head;
	node* slow = head;
	while (fast != NULL && fast->next != NULL)
	{
		slow = slow->next;
		fast = fast->next->next;
		if (fast == slow) return slow;
	}
	return NULL;
}

void removecycle(node* head)
{
	if (cycle(head))
	{
		node* temp = head;
		node* slow = cycle(head);
		node* prev = NULL;
		while (temp != slow)
		{
			prev = slow;
			temp = temp->next;
			slow = slow->next;
		}
	}
}
int main()
{
	node* head = NULL;
	takeinput(head);
	// int k; cin >> k;
	// kthfromlast(head, k);
	// printlist(head); cout << endl;
	// head = deletenafterm(head, 3, 5);
	// printlist(head);
	// 1 2 3 4 5 6 7 8 9 10 -1


	// deletemiddle(head);
	// node* head1 = itreverse(head);
	// printlist(head1); cout << endl;
	node* head2 = recreverse(head);
	printlist(head2); cout << endl;

	return 0;
}



// class Solution {
// public:
//     void getmiddle(ListNode*& head,ListNode*& middle,ListNode*& prev)
//     {
//         ListNode* fast=head;
//         ListNode* slow=head;
//         while(fast!=NULL&&fast->next!=NULL)
//         {
//             prev=slow;
//             slow=slow->next;
//             fast=fast->next->next;
//         }
//         middle=slow;
//     }
//     void itreverse(ListNode*& head)
//     {
//         ListNode* dummy=NULL;
//         while(head!=NULL)
//         {
//             ListNode* next=head->next;
//             head->next=dummy;
//             dummy=head;
//             head=next;
//         }
//         head=dummy;
//     }
//     bool isPalindrome(ListNode* head) {
//         //a b c d e
//         //a b c d e f
//         ListNode* middle;
//         ListNode* prev;
//         getmiddle(head,middle,prev);
//         prev->next=NULL;

//         itreverse(middle);

//         bool ans=true;
//         while(head!=NULL&&middle!=NULL)
//         {
//             if(head->val!=middle->val){
//                 ans=false; break;
//             }
//             head=head->next;
//             middle=middle->next;
//         }
//         return ans;

//     }
// };