Kame3

Спој листи најизменично (лаб листа)

Nov 25th, 2020 (edited)
609
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Дадени се две еднострано поврзани листи чии што јазли содржат по еден природен број. Треба да се спојат двете листи во една резултантна на тој начин што наизменично прво ќе се додаваат првите два јазли од првата листа во резултантната, па првите два од втората листа, па следните два од првата, па следните два од втората итн. Јазлите што ќе останат треба да се додадат на крај во резултантната листа, прво оние што останале од првата листа, потоа оние што останале од втората листа.
  2.  
  3. Во првиот ред од влезот се дадени броевите од кои се составени јазлите по редослед во првата листа, а во вториот ред броевите од кои се составени јазлите по редослед во втората листа. На излез треба да се испечатат јазлите по редослед во резултантната споена листа.
  4.  
  5. Забелешка: Да се креира податочна структура еднострано поврзана листа и истата да се искористи во задачата.
  6. import java.io.BufferedReader;
  7. import java.io.IOException;
  8. import java.io.InputStreamReader;
  9.  
  10. Sample input:
  11. 46
  12. 110 116 121 110 120 116 101 103 119 109 100 108 117 114 122 104 115 108 114 106 101 100 115 118 113 100 110 104 103 97 110 104 105 111 106 106 114 107 99 115 97 98 102 111 117 121
  13. 47
  14. 99 117 99 119 107 100 98 105 102 118 102 115 112 109 105 108 120 106 122 117 104 108 103 112 114 105 113 119 117 97 99 105 107 104 108 111 115 105 116 113 116 101 115 114 114 118 122
  15.  
  16. Sample output:
  17. 110 116 99 117 121 110 99 119 120 116 107 100 101 103 98 105 119 109 102 118 100 108 102 115 117 114 112 109 122 104 105 108 115 108 120 106 114 106 122 117 101 100 104 108 115 118 103 112 113 100 114 105 110 104 113 119 103 97 117 97 110 104 99 105 105 111 107 104 106 106 108 111 114 107 115 105 99 115 116 113 97 98 116 101 102 111 115 114 117 121 114 118 122
  18.  
  19.  
  20.  
  21.  
  22. import java.io.BufferedReader;
  23. import java.io.IOException;
  24. import java.io.InputStreamReader;
  25.  
  26. Sample input:
  27. 46
  28. 110 116 121 110 120 116 101 103 119 109 100 108 117 114 122 104 115 108 114 106 101 100 115 118 113 100 110 104 103 97 110 104 105 111 106 106 114 107 99 115 97 98 102 111 117 121
  29. 47
  30. 99 117 99 119 107 100 98 105 102 118 102 115 112 109 105 108 120 106 122 117 104 108 103 112 114 105 113 119 117 97 99 105 107 104 108 111 115 105 116 113 116 101 115 114 114 118 122
  31.  
  32. Sample output:
  33. 110 116 99 117 121 110 99 119 120 116 107 100 101 103 98 105 119 109 102 118 100 108 102 115 117 114 112 109 122 104 105 108 115 108 120 106 114 106 122 117 101 100 104 108 115 118 103 112 113 100 114 105 110 104 113 119 103 97 117 97 110 104 99 105 105 111 107 104 106 106 108 111 114 107 115 105 99 115 116 113 97 98 116 101 102 111 115 114 117 121 114 118 122 */
  34.  
  35. import java.io.BufferedReader;
  36. import java.io.IOException;
  37. import java.io.InputStreamReader;
  38.  
  39. class SLLNode<E>
  40. {
  41.     E element;
  42.     SLLNode<E> succ;
  43.    
  44.     SLLNode(){}
  45.     SLLNode(E element, SLLNode<E> succ)
  46.     {
  47.         this.element=element;
  48.         this.succ=succ;
  49.     }
  50. }
  51. class SLL<E>
  52. {
  53.     SLLNode<E> first;
  54.     SLL()
  55.     {
  56.         first=null;
  57.     }
  58.     public void insertFirst(E element)
  59.     {
  60.         SLLNode<E> nov = new SLLNode<>(element,first);
  61.         first = nov;
  62.     }
  63.     public void insertLast(E element)
  64.     {
  65.         if(first==null) insertFirst(element);
  66.         else
  67.         {
  68.             SLLNode<E> dvizi = first;
  69.             while(dvizi.succ != null)
  70.             {
  71.                 dvizi = dvizi.succ;
  72.             }
  73.         SLLNode<E> last = new SLLNode<>(element,null);
  74.         dvizi.succ=last;
  75.         }
  76.     }
  77.     public void insertAfter(E element, SLLNode<E>node)
  78.     {
  79.         if(node!=null){
  80.             SLLNode<E> nov = new SLLNode<>(element,node.succ);
  81.             node.succ = nov;
  82.         }
  83.     }
  84.    
  85.     public int getLength()
  86.     {
  87.         SLLNode<E> dvizi = first;
  88.         int length = 0;
  89.         while(dvizi!=null)
  90.         {
  91.             length++;
  92.             dvizi = dvizi.succ;
  93.         }
  94.         return length;
  95.     }
  96.    
  97.    
  98.     public String toString()
  99.     {
  100.         String s = new String();
  101.         SLLNode<E> dvizi = first;
  102.         while(dvizi!=null)
  103.         {
  104.             s = s+dvizi.element+" ";
  105.             dvizi=dvizi.succ;
  106.         }
  107.         return s;
  108.     }
  109.     public SLLNode<E> getFirst()
  110.     {
  111.         return first;
  112.     }
  113.    
  114. }
  115.  
  116. public class SpecialSLLJoin {
  117.    
  118.     private static SLL<Integer> specialJoin(SLL<Integer> lista1,
  119.             SLL<Integer> lista2) {
  120.        
  121.         SLL<Integer> spoenaLista = new SLL<>();
  122.         SLLNode<Integer> firstL1 = lista1.getFirst();
  123.         SLLNode<Integer> firstL2 = lista2.getFirst();
  124.         int br1,br2;
  125.        
  126.         while((firstL1 != null)||(firstL2!=null))
  127.         {
  128.             br1=0;br2=0;
  129.             while((firstL1!=null)&&(br1!=2))
  130.             {
  131.                 spoenaLista.insertLast(firstL1.element);
  132.                 firstL1 = firstL1.succ;
  133.                 br1++;
  134.             }
  135.             while((firstL2!=null)&&(br2!=2))
  136.             {
  137.                 spoenaLista.insertLast(firstL2.element);
  138.                 firstL2 = firstL2.succ;
  139.                 br2++;
  140.             }
  141.         }
  142.         return spoenaLista;
  143.     }
  144.    
  145.    
  146.     public static void main(String[] args) throws IOException{
  147.        
  148.         SLL<Integer> lista1 = new SLL<>();
  149.         SLL<Integer> lista2 = new SLL<>();
  150.    
  151.         BufferedReader stdin = new BufferedReader(new InputStreamReader(
  152.                 System.in));
  153.         String s = stdin.readLine();
  154.         int N = Integer.parseInt(s);
  155.         s = stdin.readLine();
  156.         String[] pomniza = s.split(" ");
  157.         for (int i = 0; i < N; i++) {
  158.             lista1.insertLast(Integer.parseInt(pomniza[i]));
  159.         }
  160.  
  161.         s = stdin.readLine();
  162.         N = Integer.parseInt(s);
  163.         s = stdin.readLine();
  164.         pomniza = s.split(" ");
  165.         for (int i = 0; i < N; i++) {
  166.             lista2.insertLast(Integer.parseInt(pomniza[i]));
  167.         }
  168.        
  169.         SLL<Integer> spoeni = specialJoin(lista1,lista2);
  170.         System.out.println(spoeni);
  171.        
  172.     }
  173.  
  174.    
  175. }
RAW Paste Data