Question

Implement a singly linked list having all unique elements with the following operations.I 0 x – Inserts element x at the end.
I 1 y x – If the element y exists, then insert element x after the element y, else insert element y before the existing element x. Assuming either the element x or the element y exists.
I 2 z y x – Inserts element x in the middle of the elements z and y. The element z appears before the element y.
U x p – Links the next pointer of the element x to the node lying at the pth position from the element x while traversing towards right. In case of insufficient number of nodes, the counting continues by updating the existing linked list to its circular version.
Input:
Line 1 contains an integer N indicating the total number of operations.
Each of the following N lines contains an operation to be performed in the format as is described above.
Output:
Line 1 has 1 if the linked list gets updated to its circular version, else 0.
Line 2 has a count of the number of nodes whose addresses are contained in the next pointer of multiple nodes. If output at Line 2 is zero then output Line 4 will not be printed.
Line 3 has space separated contents of all the nodes which are counted to get the output at Line 2 in increasing order. If output at Line 2 is zero then output Line 3 will have space separated contents of the generated linked list.
Line 4 has space separated respective frequencies of each output value, say x, at Line 3. 'Frequency of each output value x' means the count of multiple nodes whose next pointers have address of a node with this value x.
Constraints
All integers range in between 1 and 1000.
Sample Input I:
3
I 0 1
I 1 1 7
I 2 1 7 3
Sample Output I:
0
0
1 3 7
EXPLANATION I:
Linked list after execution of each of the three operations given in the input is shown below.

1

1 - > 7

1 - > 3 - > 7

Sample Input II:
10
I 0 1
I 0 7
I 1 6 7
I 1 1 2
I 2 1 7 3
I 2 3 6 5
I 2 1 7 4
U 2 3
U 2 2
U 1 6
Sample Output II:
1
1
6
3

Answer 1

CODE:

#include <iostream>

#include<map>

#include<vector>

#include<algorithm>

#include<cmath>

using namespace std;

class Node

{

public:

int val;

Node *next;

Node(int x)

{

this->next=NULL;this->val=x;

}

};

int searchPos(Node *head,int x)//search position of x

{

int c=0;

Node *temp=head;

while(temp!=NULL)

{

c++;

if(temp->val==x)

break;

temp=temp->next;

  

}

return c;

}

void insert(Node *head,int x,int pos,map<int,vector<Node*>> &m)//inserts node at pos x n updates map too

{

int l=pos;

l-=2;

Node *temp=head;

while(l--)

temp=temp->next;

Node *p=temp->next;

temp->next=new Node(x);

x->next=p;

m[x].push_back(temp);

}

int main()

{

int n;

cin>>n;

Node *head=NULL,*tail=head;

map<int,vector<Node*>>m;//map to store current node value n prev node addresses,traversal becomes easy

while(n--)

{ string s;

int circular=0;//circular list or not

getline(cin,s);

vector<string> v;

boost::split(v, s, boost::is_any_of(" ")); //splitting string

int len=v.size();

if(v[0]=='I')

{

if(len==3)

{

if(head==NULL)//empty list

{ head=new Node(v[2]);tail=head;m[v[2]].push_back(NULL);}

else//not empty list

{

tail->next=new Node(v[2]);

m[v[2]].push_back(tail);//push to map

tail=tail->next;

  

}

}

else if(len==4)

{

if(m.find(v[2])!=m.end())//adding next to y

{

Node *temp=head;

while(temp!=NULL && temp->val!=v[2])

temp=temp->next;

Node *x=new Node(v[3]);

x->next=temp->next;

temp->next=x;

m[v[3]].push_back(temp);

}

else//adding before x

{

Node *p=m[v[3]];

Node *cur=p->next;

Node *x=new Node(v[2]);

if(p==NULL)

{

head=x;

x->next=cur;

m[x].push_back(NULL);

}

else

{

x->next=p->next;

p->next=x;

m[x].push_back(p);

}

}

}

else

{

int a,b,c;

a=searchPos(v[2]);//position of y

b=searchPos(v[3]);//position of z

c=ceil((a+b)/2);//calcute mid position for inserting x between y and z

insert(head,v[4],c,m);

}

}

else

{

int a,b,c=0;

a=v[1];

b=v[2];

Node *temp=head;

while(temp)//searching for x

{

if(temp->val==a)

break;

temp=temp->next;

}

Node *x=temp;

while(b--)//traversing p nodes from x

{

if(temp->next==NULL)//making it circular

{temp->next=head;circular=1;}

else

temp=temp->next;

  

}

x->next=temp;

m[temp->val].push_back(x);

}

}

int count=0;

vector<pair<int,int>>s;

for(auto x:m)

{

if(x->second.size()>1)

{ count+=1;

s.push_back(x->first,x->second.size());

}

}

sort(s.begin(),s.end())//sorting the nodes having multiple prev nodes

if(circular!=0)

cout<<"1"<<"\n";

else

cout<<"0\n";

cout<<count<<"\n";//count of nodes with multiple pre nodes

int p=s.size();

  

if(p!=0)

{

for(auto x:s)

cout<<x.first<<" ";

cout<<"\n";

for(auto x:s)

cout<<x.second<<" ";

cout<<"\n";

}

else//if there is no node with multiple pre nodes,print original linked list

{

Node *temp=head;

while(temp!=NULL)

{

cout<<temp->val<<" ";temp=temp->next;

}

cout<<"\n";

}

return 0;

}