fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Node {
  5.     int val;
  6.     Node* next;
  7. };
  8.  
  9.  
  10. Node* InsertAtBegin(Node* root, int x) {
  11.     Node* newnode = new Node();
  12.     newnode->val = x;
  13.     newnode->next = NULL;
  14. if(root==NULL)
  15. {
  16. root=newnode;
  17.     return root;
  18. }
  19. else
  20. {
  21. newnode->next=root;
  22. root=newnode;
  23. return root;
  24. }
  25. }
  26. Node*InsertAtEnd(Node*root,int x)
  27. {
  28. Node*newnode=new Node();
  29. newnode->next=NULL;
  30. newnode->val=x;
  31. if(root==NULL)
  32. {
  33. root=newnode;
  34. return root;
  35. }
  36. Node*currnode;
  37. currnode=root;
  38. while(currnode->next!=NULL)
  39. {
  40. currnode=currnode->next;
  41. }
  42. currnode->next=newnode;
  43. return root;
  44. }
  45. Node*InsertAtPos(Node*root,int x,int pos)
  46. {
  47. if(pos==0)
  48. {
  49. root=InsertAtBegin(root,x);
  50. }
  51. else
  52. {
  53. Node*newnode=new Node();
  54. newnode->val=x;
  55. newnode->next=NULL;
  56. Node*currnode;
  57. currnode=root;
  58. for(int i=1;i<pos && currnode!=NULL;i++)
  59. {
  60. currnode=currnode->next;
  61. }
  62. newnode->next=currnode->next;
  63. currnode->next=newnode;
  64. }
  65. return root;
  66. }
  67. Node*SortedInsert(Node*root,int x)
  68. {
  69. Node*newnode=new Node();
  70. newnode->val=x;
  71. newnode->next=NULL;
  72. Node*currnode,*prevnode;
  73. currnode=root;
  74. prevnode=NULL;
  75. if(root==NULL)
  76. {
  77. root=newnode;
  78. return root;
  79. }
  80. if(x<root->val)
  81. {
  82. newnode->next=root;
  83. root=newnode;
  84. return root;
  85. }
  86.  
  87. while(currnode!=NULL)
  88. {
  89. if(currnode->val<x)
  90. {
  91. prevnode=currnode;
  92. currnode=currnode->next;
  93. }
  94. else
  95. {
  96. prevnode->next=newnode;
  97. newnode->next=currnode;
  98. return root;
  99. }
  100. prevnode->next=newnode;
  101. newnode->next=NULL;
  102. }
  103. return root;
  104. }
  105. int Search(Node*root,int x)
  106. {
  107. int pos=0;
  108. Node*currnode;
  109. currnode=root;
  110. while(currnode!=NULL)
  111. {
  112. if(currnode->val==x)
  113. {
  114. return pos;
  115. }
  116. else
  117. {
  118. currnode=currnode->next;
  119. pos++;
  120. }
  121. }
  122. return -1;
  123. }
  124. Node*Delete(Node*root,int x)
  125. {
  126. Node*currnode,*prevnode;
  127. currnode=root;
  128. prevnode=NULL;
  129. while(currnode!=NULL)
  130. {
  131. if(currnode->val!=x)
  132. {
  133. prevnode=currnode;
  134. currnode=currnode->next;
  135. }
  136. else
  137. {
  138. if(currnode==root)
  139. {
  140. root=root->next;
  141. delete(currnode);
  142. }
  143. else
  144. {
  145. prevnode->next=currnode->next;
  146. delete(currnode);
  147. }
  148. break;
  149. }
  150. }
  151. return root;
  152. }
  153. void Print(Node* root) {
  154.     Node* currnode = root;
  155.     while (currnode != NULL) {
  156.         cout << currnode->val << " ";
  157.         currnode = currnode->next;
  158.     }
  159.     cout << endl;
  160. }
  161.  
  162. int main() {
  163.     Node* root = NULL;
  164.     int n;
  165.     cin >> n; 
  166. if(n<=0)
  167. {
  168. cout<<endl;
  169. return 0;
  170. }
  171.     int a[n];
  172.     for (int i = 0; i < n; i++) {
  173.         cin >> a[i]; 
  174.     }
  175.  
  176.     Print(root);
  177.     for (int i = 0; i < n; i++) {
  178.         root = InsertAtBegin(root, a[i]);
  179.     }
  180.  
  181.  
  182.     Print(root);
  183. for(int i=0;i<n;i++)
  184. {
  185. root=InsertAtEnd(root,a[i]);
  186. }
  187. Print(root);
  188.  
  189. root=InsertAtPos(root,5,0);
  190. root=InsertAtPos(root,8,3);
  191.  
  192. Print(root);
  193. for(int i=0;i<n;i++)
  194. {
  195. root=SortedInsert(root,a[i]);
  196. }
  197. Print(root);
  198. for(int i=0;i<n;i++)
  199. {
  200. cout<<"Positions of "<<a[i]<<":"<<Search(root,a[i])<<endl;
  201. }
  202. for(int i=0;i<n;i++)
  203. {
  204. root=Delete(root,a[i]);
  205. }
  206. Print(root);
  207.     return 0;
  208. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
3
7 3 8
stdout
copy 
8 3 7 
8 3 7 7 3 8 
5 8 3 8 7 7 3 8 
3 8 8 3 8 7 7 3 8 
Positions of 7:5
Positions of 3:0
Positions of 8:1
8 3 8 7 3 8
https://ideone.com/3dgWnX
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!