Stamenco

АПС - Спој листи наизменично

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