Advertisement
Guest User

Untitled

a guest
Oct 21st, 2014
186
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.92 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.  
  7. class SLLNode<E extends Comparable<E>> {
  8. protected E element;
  9. protected SLLNode<E> succ;
  10.  
  11. public SLLNode(E elem, SLLNode<E> succ) {
  12. this.element = elem;
  13. this.succ = succ;
  14. }
  15.  
  16. @Override
  17. public String toString() {
  18. return element.toString();
  19. }
  20. }
  21.  
  22. class SLL<E extends Comparable<E>> {
  23. private SLLNode<E> first;
  24.  
  25. public SLL() {
  26. // Construct an empty SLL
  27. this.first = null;
  28. }
  29.  
  30. public void deleteList() {
  31. first = null;
  32. }
  33.  
  34. public int length() {
  35. int ret;
  36. if (first != null) {
  37. SLLNode<E> tmp = first;
  38. ret = 1;
  39. while (tmp.succ != null) {
  40. tmp = tmp.succ;
  41. ret++;
  42. }
  43. return ret;
  44. } else
  45. return 0;
  46.  
  47. }
  48.  
  49. @Override
  50. public String toString() {
  51. String ret = new String();
  52. if (first != null) {
  53. SLLNode<E> tmp = first;
  54. ret += tmp + "->";
  55. while (tmp.succ != null) {
  56. tmp = tmp.succ;
  57. ret += tmp + "->";
  58. }
  59. } else
  60. ret = "Prazna lista!!!";
  61. return ret;
  62. }
  63.  
  64. public void insertFirst(E o) {
  65. SLLNode<E> ins = new SLLNode<E>(o, first);
  66. first = ins;
  67. }
  68.  
  69. public void insertAfter(E o, SLLNode<E> node) {
  70. if (node != null) {
  71. SLLNode<E> ins = new SLLNode<E>(o, node.succ);
  72. node.succ = ins;
  73. } else {
  74. System.out.println("Dadenot jazol e null");
  75. }
  76. }
  77.  
  78. public void insertBefore(E o, SLLNode<E> before) {
  79.  
  80. if (first != null) {
  81. SLLNode<E> tmp = first;
  82. if (first == before) {
  83. this.insertFirst(o);
  84. return;
  85. }
  86. // ako first!=before
  87. while (tmp.succ != before)
  88. tmp = tmp.succ;
  89. if (tmp.succ == before) {
  90. SLLNode<E> ins = new SLLNode<E>(o, before);
  91. tmp.succ = ins;
  92. } else {
  93. System.out.println("Elementot ne postoi vo listata");
  94. }
  95. } else {
  96. System.out.println("Listata e prazna");
  97. }
  98. }
  99.  
  100. public void insertLast(E o) {
  101. if (first != null) {
  102. SLLNode<E> tmp = first;
  103. while (tmp.succ != null)
  104. tmp = tmp.succ;
  105. SLLNode<E> ins = new SLLNode<E>(o, null);
  106. tmp.succ = ins;
  107. } else {
  108. insertFirst(o);
  109. }
  110. }
  111.  
  112. public SLLNode<E> getFirst() {
  113. return first;
  114. }
  115.  
  116. public Iterator<E> iterator() {
  117. // Return an iterator that visits all elements of this list, in
  118. // left-to-right order.
  119. return new LRIterator<E>();
  120. }
  121.  
  122. // //////////Inner class ////////////
  123.  
  124. private class LRIterator<E extends Comparable<E>> implements Iterator<E> {
  125.  
  126. private SLLNode<E> place;
  127.  
  128. @SuppressWarnings("unchecked")
  129. private LRIterator() {
  130. place = (SLLNode<E>) first;
  131. }
  132.  
  133. public boolean hasNext() {
  134. return (place != null);
  135. }
  136.  
  137. public E next() {
  138. if (place == null)
  139. throw new NoSuchElementException();
  140. E nextElem = place.element;
  141. place = place.succ;
  142. return nextElem;
  143. }
  144.  
  145. @Override
  146. public void remove() {
  147. // TODO Auto-generated method stub
  148.  
  149. }
  150.  
  151. }
  152.  
  153. public SLL<E> joinLists(SLL<E> in) {
  154. // Vashiot kod tuka...
  155.  
  156. int dolzinaLista1 = this.length();
  157. int dolzinaLista2 = in.length();
  158.  
  159. if (dolzinaLista1 <= dolzinaLista2)
  160. return makeTheJoin(this, in, dolzinaLista1);
  161. else
  162. return makeTheJoin(this, in, dolzinaLista2);
  163. }
  164.  
  165. private SLL<E> makeTheJoin(SLL<E> pomalataLista, SLL<E> pogolemataLista,
  166. int pomala) {
  167. SLL<E> res = new SLL<E>();
  168. SLLNode<E> tmp1 = pomalataLista.getFirst();
  169. SLLNode<E> tmp2 = pogolemataLista.getFirst();
  170.  
  171. for (int i = 1; i <= pomala; ++i) {
  172. if (i % 2 != 0) {
  173. res.insertLast(tmp1.element);
  174. tmp1 = tmp1.succ;
  175.  
  176. if (tmp1 != null) {
  177. res.insertLast(tmp1.element);
  178. tmp1 = tmp1.succ;
  179. }
  180. } else if (i % 2 == 0) {
  181. res.insertLast(tmp2.element);
  182. tmp2 = tmp2.succ;
  183.  
  184. if (tmp2 != null) {
  185. res.insertLast(tmp2.element);
  186. tmp2 = tmp2.succ;
  187. }
  188. }
  189.  
  190. }
  191.  
  192. while (tmp2 != null) {
  193. res.insertLast(tmp2.element);
  194. tmp2 = tmp2.succ;
  195. }
  196.  
  197. while (tmp1 != null) {
  198. res.insertLast(tmp1.element);
  199. tmp1 = tmp1.succ;
  200. }
  201.  
  202. return res;
  203. }
  204.  
  205. }
  206.  
  207. public class SLLJoinLists {
  208. public static void main(String[] args) throws IOException {
  209.  
  210. SLL<Integer> lista1 = new SLL<Integer>(), lista2 = new SLL<Integer>();
  211. BufferedReader stdin = new BufferedReader(new InputStreamReader(
  212. System.in));
  213. String s = stdin.readLine();
  214. int N = Integer.parseInt(s);
  215. s = stdin.readLine();
  216. String[] pomniza = s.split(" ");
  217. for (int i = 0; i < N; i++) {
  218. lista1.insertLast(Integer.parseInt(pomniza[i]));
  219. }
  220.  
  221. s = stdin.readLine();
  222. N = Integer.parseInt(s);
  223. s = stdin.readLine();
  224. pomniza = s.split(" ");
  225. for (int i = 0; i < N; i++) {
  226. lista2.insertLast(Integer.parseInt(pomniza[i]));
  227. }
  228.  
  229. SLL<Integer> spoeni = lista1.joinLists(lista2);
  230. Iterator<Integer> it = spoeni.iterator();
  231. while (it.hasNext()) {
  232. System.out.print(it.next());
  233. if (it.hasNext())
  234. System.out.print(" ");
  235. }
  236. System.out.println();
  237. }
  238. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement