SashkoKlincharov

[Java][АПС] - List mirror between two intervals

Feb 6th, 2020
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.48 KB | None | 0 0
  1. import java.util.Iterator;
  2. import java.util.NoSuchElementException;
  3. import java.util.Scanner;
  4.  
  5. class SLL<E> {
  6. private SLLNode<E> first;
  7.  
  8. public SLL() {
  9. // Construct an empty SLL
  10. this.first = null;
  11. }
  12.  
  13. public void deleteList() {
  14. first = null;
  15. }
  16.  
  17. public int length() {
  18. int ret;
  19. if (first != null) {
  20. SLLNode<E> tmp = first;
  21. ret = 1;
  22. while (tmp.succ != null) {
  23. tmp = tmp.succ;
  24. ret++;
  25. }
  26. return ret;
  27. } else
  28. return 0;
  29.  
  30. }
  31.  
  32. @Override
  33. public String toString() {
  34. String ret = new String();
  35. if (first != null) {
  36. SLLNode<E> tmp = first;
  37. ret += tmp + "->";
  38. while (tmp.succ != null) {
  39. tmp = tmp.succ;
  40. ret += tmp + "->";
  41. }
  42. } else
  43. ret = "Prazna lista!!!";
  44. return ret;
  45. }
  46.  
  47. public void insertFirst(E o) {
  48. SLLNode<E> ins = new SLLNode<E>(o, first);
  49. first = ins;
  50. }
  51.  
  52. public void insertAfter(E o, SLLNode<E> node) {
  53. if (node != null) {
  54. SLLNode<E> ins = new SLLNode<E>(o, node.succ);
  55. node.succ = ins;
  56. } else {
  57. System.out.println("Dadenot jazol e null");
  58. }
  59. }
  60.  
  61. public void insertBefore(E o, SLLNode<E> before) {
  62.  
  63. if (first != null) {
  64. SLLNode<E> tmp = first;
  65. if(first==before){
  66. this.insertFirst(o);
  67. return;
  68. }
  69. //ako first!=before
  70. while (tmp.succ != before)
  71. tmp = tmp.succ;
  72. if (tmp.succ == before) {
  73. SLLNode<E> ins = new SLLNode<E>(o, before);
  74. tmp.succ = ins;
  75. } else {
  76. System.out.println("Elementot ne postoi vo listata");
  77. }
  78. } else {
  79. System.out.println("Listata e prazna");
  80. }
  81. }
  82.  
  83. public void insertLast(E o) {
  84. if (first != null) {
  85. SLLNode<E> tmp = first;
  86. while (tmp.succ != null)
  87. tmp = tmp.succ;
  88. SLLNode<E> ins = new SLLNode<E>(o, null);
  89. tmp.succ = ins;
  90. } else {
  91. insertFirst(o);
  92. }
  93. }
  94.  
  95. public E deleteFirst() {
  96. if (first != null) {
  97. SLLNode<E> tmp = first;
  98. first = first.succ;
  99. return tmp.element;
  100. } else {
  101. System.out.println("Listata e prazna");
  102. return null;
  103. }
  104. }
  105.  
  106. public E delete(SLLNode<E> node) {
  107. if (first != null) {
  108. SLLNode<E> tmp = first;
  109. if(first ==node){
  110. return this.deleteFirst();
  111. }
  112. while (tmp.succ != node && tmp.succ.succ != null)
  113. tmp = tmp.succ;
  114. if (tmp.succ == node) {
  115. tmp.succ = tmp.succ.succ;
  116. return node.element;
  117. } else {
  118. System.out.println("Elementot ne postoi vo listata");
  119. return null;
  120. }
  121. } else {
  122. System.out.println("Listata e prazna");
  123. return null;
  124. }
  125.  
  126. }
  127.  
  128. public SLLNode<E> getFirst() {
  129. return first;
  130. }
  131.  
  132. public SLLNode<E> find(E o) {
  133. if (first != null) {
  134. SLLNode<E> tmp = first;
  135. while (tmp.element != o && tmp.succ != null)
  136. tmp = tmp.succ;
  137. if (tmp.element == o) {
  138. return tmp;
  139. } else {
  140. System.out.println("Elementot ne postoi vo listata");
  141. }
  142. } else {
  143. System.out.println("Listata e prazna");
  144. }
  145. return first;
  146. }
  147.  
  148. public Iterator<E> iterator () {
  149. // Return an iterator that visits all elements of this list, in left-to-right order.
  150. return new LRIterator<E>();
  151. }
  152.  
  153. // //////////Inner class ////////////
  154.  
  155. private class LRIterator<E> implements Iterator<E> {
  156.  
  157. private SLLNode<E> place, curr;
  158.  
  159. private LRIterator() {
  160. place = (SLLNode<E>) first;
  161. curr = null;
  162. }
  163.  
  164. public boolean hasNext() {
  165. return (place != null);
  166. }
  167.  
  168. public E next() {
  169. if (place == null)
  170. throw new NoSuchElementException();
  171. E nextElem = place.element;
  172. curr = place;
  173. place = place.succ;
  174. return nextElem;
  175. }
  176.  
  177. public void remove() {
  178. //Not implemented
  179. }
  180. }
  181.  
  182. public void mirror(){
  183. if (first != null) {
  184. //m=nextsucc, p=tmp,q=next
  185. SLLNode<E> tmp = first;
  186. SLLNode<E> newsucc = null;
  187. SLLNode<E> next;
  188.  
  189. while(tmp != null){
  190. next = tmp.succ;
  191. tmp.succ = newsucc;
  192. newsucc = tmp;
  193. tmp = next;
  194. }
  195. first = newsucc;
  196. }
  197.  
  198. }
  199.  
  200. public void merge (SLL<E> in){
  201. if (first != null) {
  202. SLLNode<E> tmp = first;
  203. while(tmp.succ != null)
  204. tmp = tmp.succ;
  205. tmp.succ = in.getFirst();
  206. }
  207. else{
  208. first = in.getFirst();
  209. }
  210. }
  211. }
  212. class SLLNode<E> {
  213. protected E element;
  214. protected SLLNode<E> succ;
  215.  
  216. public SLLNode(E elem, SLLNode<E> succ) {
  217. this.element = elem;
  218. this.succ = succ;
  219. }
  220.  
  221. @Override
  222. public String toString() {
  223. return element.toString();
  224. }
  225. }
  226.  
  227. public class SLLMirror {
  228. public static SLL<Integer> mirror(SLL<Integer> lista,int a,int b){
  229. SLLNode<Integer> tmp = lista.getFirst();
  230. SLLNode<Integer> p = null;
  231. SLLNode<Integer> q = null;
  232. SLLNode<Integer> pred = null;
  233. int j = 0;
  234. while(tmp.element!=a) {
  235. pred = tmp;
  236. tmp = tmp.succ;
  237. }
  238. p = tmp;
  239. q = tmp;
  240. while(tmp.element!=b) {
  241. if(tmp.element==b)
  242. break;
  243. j++;
  244. tmp = tmp.succ;
  245. }
  246. int i = 0;
  247. while(i<j) {
  248. int k = 0;
  249. while(k<j) {
  250. q = q.succ;
  251. ++k;
  252. }
  253. SLLNode<Integer> help1 = p;
  254. SLLNode<Integer> help2 = q;
  255. lista.insertBefore(help2.element, p);
  256. p = p.succ;
  257. int item = help1.element;
  258. lista.delete(help1);
  259. lista.insertBefore(item, q);
  260. q = pred.succ;
  261. lista.delete(help2);
  262. i++;
  263. j--;
  264. }
  265. return lista;
  266. }
  267. public static void main(String[] args) {
  268. Scanner input = new Scanner(System.in);
  269. int n = input.nextInt();
  270.  
  271. SLL<Integer> lista = new SLL<Integer>();
  272. for(int i=0;i<n;i++)
  273. lista.insertLast(input.nextInt());
  274.  
  275. int a = input.nextInt();
  276. int b = input.nextInt();
  277. System.out.println(mirror(lista,a,b));
  278.  
  279. }
  280.  
  281. }
Add Comment
Please, Sign In to add comment