DamSi

Untitled

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