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*DeleteFromBegin(Node*root)
  125. {
  126. if(root==NULL)
  127. return NULL;
  128.  
  129. Node*temp;
  130. temp=root;
  131. root=root->next;
  132. delete temp;
  133. return root;
  134. }
  135. Node*DeleteFromPos(Node*root,int pos)
  136. {
  137. if(root==NULL || pos<0)
  138. return root;
  139. if(pos==0)
  140. {
  141. return DeleteFromBegin(root);
  142. }
  143. Node*currnode=root;
  144. Node*prevnode=NULL;
  145. int count=0;
  146. while(currnode!=NULL && count<pos)
  147. {
  148. prevnode=currnode;
  149. currnode=currnode->next;
  150. count++;
  151. }
  152. if(currnode!=NULL)
  153. {
  154. prevnode->next=currnode->next;
  155. delete currnode;
  156. }
  157. return root;
  158. }
  159. Node*DeleteFromEnd(Node*root)
  160. {
  161. if(root==NULL)
  162. return NULL;
  163. if(root->next==NULL)
  164. {
  165. delete root;
  166. return NULL;
  167. }
  168. Node*currnode=root;
  169. while(currnode->next && currnode->next->next)
  170. {
  171. currnode=currnode->next;
  172. }
  173. Node*temp=currnode->next;
  174. currnode->next=NULL;
  175. delete temp;
  176. return root;
  177. }
  178.  
  179. void Print(Node* root) {
  180.     Node* currnode = root;
  181.     while (currnode != NULL) {
  182.         cout << currnode->val << "→";
  183.         currnode = currnode->next;
  184.     }
  185.     cout << endl;
  186. }
  187.  
  188. int main() {
  189.     Node* root = NULL;
  190.     int n;
  191.     cin >> n; 
  192. if(n<=0)
  193. {
  194. cout<<endl;
  195. return 0;
  196. }
  197.     int a[n];
  198.     for (int i = 0; i < n; i++) {
  199.         cin >> a[i]; 
  200.     }
  201.  
  202.     Print(root);
  203.     for (int i = 0; i < n; i++) {
  204.         root = InsertAtBegin(root, a[i]);
  205.     }
  206.  
  207.  
  208.     Print(root);
  209. for(int i=0;i<n;i++)
  210. {
  211. root=InsertAtEnd(root,a[i]);
  212. }
  213. Print(root);
  214.  
  215. root=InsertAtPos(root,5,0);
  216. root=InsertAtPos(root,8,3);
  217.  
  218. Print(root);
  219. for(int i=0;i<n;i++)
  220. {
  221. root=SortedInsert(root,a[i]);
  222. }
  223. Print(root);
  224. for(int i=0;i<n;i++)
  225. {
  226. cout<<"Positions of "<<a[i]<<":"<<Search(root,a[i])<<endl;
  227. }
  228. for(int i=0;i<n;i++)
  229. {
  230.  
  231. root=DeleteFromPos(root,0);
  232.  
  233. }
  234. Print(root);
  235.     return 0;
  236. }
Success #stdin #stdout 0s 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
3→8→7→7→3→8→
https://ideone.com/fDGLys
language:
C++ (gcc 8.3)
created:
12 hours 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!