#include
using namespace std;
class node{
public:
int data;
node* next;
node(int d)
{
data = d;
next = NULL;
}
};
void insert_at_head(node *&head,int d)
{
node *n = new node(d);
n->next = head;
head = n;
}
void insert_at_tail(node *&head,int d)
{
node *temp = head;
if(head==NULL)
{
head = new node(d);
return;
}
int jump = 1;
while(temp->next!=NULL)
{
temp = temp->next;
}
node *n = new node(d);
temp->next = n;
return;
}
int length(node *head)
{
int pos = 0;
while(head!=NULL)
{
head = head->next;
pos++;
}
return pos;
}
void insert_at_middle(node *&head,int d,int pos)
{
if(head==NULL or pos==0)
{
insert_at_head(head,d);
}
else if(pos>length(head))
{
insert_at_tail(head,d);
}
else
{
int jump = 1;
node *temp = head;
while(jump<=pos)
{
temp = temp->next;
jump++;
}
node *n = new node(d);
n->next = temp->next;
temp->next = n;
}
}
void deletefromHead(node *&head)
{
if(head==NULL)
{
return;
}
node *temp = head;
head = head->next;
delete temp;
return;
}
void deletefromTail(node *&head)
{
node *temp,*prev=NULL;
temp = head;
while(temp->next!=NULL)
{
prev = temp;
temp = temp->next;
}
prev->next = NULL;
delete temp;
return;
}
void deletefromMiddle(node *&head,int pos)
{
node *prev=NULL,*temp=head;
if(head==NULL)
{
return;
}
if(pos==0)
{
deletefromHead(head);
}
if(pos>=length(head))
{
deletefromTail(head);
}
int jump = 1;
while(jump<=pos)
{
prev = temp;
temp = temp->next;
jump++;
}
prev->next = temp->next;
delete temp;
return;
}
void searchRecursively(node *&head,int val,int start)
{
// base case
node *temp = head;
if(temp->next==NULL)
{
if(temp->data==val)
{
cout<< start <<endl;
return;
}
cout<< “Not Found!”<<endl;
return;
}
if(temp->data==val)
{
cout<< start <<endl;
return;
}
searchRecursively(head->next,val,start+1);
}
void searchIteratively(node *&head,int val)
{
int start = 0;
node *temp = head;
while(temp->next!=NULL)
{
if(temp->data==val)
{
cout<<start<<endl;
return;
}
start++;
temp = temp->next;
}
if(temp->data==val)
{
cout<<start<<endl;
}
else
{
cout<<“Not found”<<endl;
}
}
void buildList(node *&head)
{
int val;
cin>>val;
while(val != -1)
{
insert_at_tail(head,val);
cin>>val;
}
}
void print(node *head)
{
while(head!=NULL)
{
cout<data<<" ";
head = head->next;
}
cout<<endl;
}
istream &operator>>(istream &is,node *&head)
{
buildList(head);
return is;
}
ostream &operator<<(ostream &os,node *&head)
{
print(head);
return os;
}
void reverse_list(node *&head)
{
node *prev = NULL;
node *curr = head;
while(curr!=NULL)
{
node *n = curr->next;
curr->next = prev;
prev = curr;
curr = n;
}
head = prev;
}
node *recursive_reverse(node *&head)
{
if(head==NULL or head->next==NULL)
{
return head;
}
node *smallpart = recursive_reverse(head->next);
node *curr = head;
curr->next->next = curr;
curr->next = NULL;
return smallpart;
}
node *mid_point(node *head)
{
if(head==NULL or head->next==NULL)
{
return head;
}
node *small = head;
node *high = head->next;
while(high!=NULL && high->next!=NULL)
{
// small move 1 step and high move 2 step
high = high->next->next;
small = small->next;
}
return small;
}
node *find_k_node(node *head,int k)
{
if(length(head)<k)
{
return head;
}
node *slow = head;
node *fast = head;
while(k–)
{
fast = fast->next;
}
while(fast!=NULL)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
int main()
{
node *head1 = NULL;
cin>>head1;
// cout<<head1<<endl;
// reverse_list(head1);
// head1 = recursive_reverse(head1);
// cout<<head1;
// node *m = mid_point(head1);
// cout<< m->data;
node *z = find_k_node(head1,3);
cout<< z->data;
return 0;
}
