Advertisement
Guest User

Untitled

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