Advertisement
mvCode

Reorder List aips

Nov 20th, 2019
132
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.77 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> {
  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> {
  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 E deleteFirst() {
  113.         if (first != null) {
  114.             SLLNode<E> tmp = first;
  115.             first = first.succ;
  116.             return tmp.element;
  117.         } else {
  118.             System.out.println("Listata e prazna");
  119.             return null;
  120.         }
  121.     }
  122.  
  123.     public E delete(SLLNode<E> node) {
  124.         if (first != null) {
  125.             SLLNode<E> tmp = first;
  126.             if(first ==node){
  127.                 return this.deleteFirst();
  128.             }
  129.             while (tmp.succ != node && tmp.succ.succ != null)
  130.                 tmp = tmp.succ;
  131.             if (tmp.succ == node) {
  132.                 tmp.succ = tmp.succ.succ;
  133.                 return node.element;
  134.             } else {
  135.                 System.out.println("Elementot ne postoi vo listata");
  136.                 return null;
  137.             }
  138.         } else {
  139.             System.out.println("Listata e prazna");
  140.             return null;
  141.         }
  142.  
  143.     }
  144.  
  145.     public SLLNode<E> getFirst() {
  146.         return first;
  147.     }
  148.  
  149.     public SLLNode<E> find(E o) {
  150.         if (first != null) {
  151.             SLLNode<E> tmp = first;
  152.             while (tmp.element != o && tmp.succ != null)
  153.                 tmp = tmp.succ;
  154.             if (tmp.element == o) {
  155.                 return tmp;
  156.             } else {
  157.                 System.out.println("Elementot ne postoi vo listata");
  158.             }
  159.         } else {
  160.             System.out.println("Listata e prazna");
  161.         }
  162.         return first;
  163.     }
  164.  
  165.     public Iterator<E> iterator () {
  166.         // Return an iterator that visits all elements of this list, in left-to-right order.
  167.         return new LRIterator<E>();
  168.     }
  169.  
  170.     // //////////Inner class ////////////
  171.  
  172.     private class LRIterator<E> implements Iterator<E> {
  173.  
  174.         private SLLNode<E> place, curr;
  175.  
  176.         private LRIterator() {
  177.             place = (SLLNode<E>) first;
  178.             curr = null;
  179.         }
  180.  
  181.         public boolean hasNext() {
  182.             return (place != null);
  183.         }
  184.  
  185.         public E next() {
  186.             if (place == null)
  187.                 throw new NoSuchElementException();
  188.             E nextElem = place.element;
  189.             curr = place;
  190.             place = place.succ;
  191.             return nextElem;
  192.         }
  193.  
  194.         public void remove() {
  195.             //Not implemented
  196.         }
  197.     }
  198.  
  199.     public void mirror(){
  200.         if (first != null) {
  201.             //m=nextsucc, p=tmp,q=next
  202.             SLLNode<E> tmp = first;
  203.             SLLNode<E> newsucc = null;
  204.             SLLNode<E> next;
  205.  
  206.             while(tmp != null){
  207.                 next = tmp.succ;
  208.                 tmp.succ = newsucc;
  209.                 newsucc = tmp;
  210.                 tmp = next;
  211.             }
  212.             first = newsucc;
  213.         }
  214.  
  215.     }
  216.  
  217.     public void merge (SLL<E> in){
  218.         if (first != null) {
  219.             SLLNode<E> tmp = first;
  220.             while(tmp.succ != null)
  221.                 tmp = tmp.succ;
  222.             tmp.succ = in.getFirst();
  223.         }
  224.         else{
  225.             first = in.getFirst();
  226.         }
  227.     }
  228. }
  229.  
  230.  
  231.  public class Preredi {
  232.  
  233.  
  234.     public static void main( String []args ) throws IOException {
  235.  
  236.         BufferedReader br = new BufferedReader( new InputStreamReader( System.in ));
  237.         String str = br.readLine();
  238.         String niza[] = str.split(" ");
  239.  
  240.         SLL<Integer> l = new<Integer> SLL();
  241.         for( int i = 0; i < niza.length; i++ ){
  242.             l.insertLast( Integer.parseInt( niza[i] ) );
  243.         }
  244.  
  245.         System.out.println( l.toString() );
  246.         System.out.println( preredi(l).toString() );
  247.     }
  248.  
  249.     public static SLL<Integer> preredi( SLL<Integer> lista )
  250.     {
  251.         SLLNode<Integer> temp = lista.getFirst();
  252.         SLLNode<Integer> iAfter = lista.getFirst();
  253.         int kolkuPati = lista.length()/2;
  254.  
  255.         for( int i=0; i< kolkuPati; i++ ){
  256.  
  257.             while( temp.succ != null )
  258.                 temp=temp.succ;
  259.  
  260.             lista.insertAfter( temp.element, iAfter );
  261.             lista.delete( temp );
  262.  
  263.             iAfter = iAfter.succ.succ;
  264.             temp = iAfter;
  265.         }
  266.  
  267.         return lista;
  268.     }
  269. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement