АПС - Подели SLL - Структури со програмирање 2013

/*
(70 поени) Дадена е единечно поврзана листа во која јазлите претставуваат цели броеви и не се сортирани. Да се напише функција која во нова единечно поврзана листа ќе ги префрли сите јазли од првата листа чие инфо поле е помало од средната вредност (целобројна) на сите јазли во првата листа. Втората листа да биде постојано сортирана во растечки редослед. Во првата листа да останат сите елементи кои не го задоволуваат овој услов.
Префрлањето на јазли од првата во втората листа да се изврши со слевање, односно да не се алоцира нова меморија за јазлите во втората листа.
Пример:
Прва листа: 5 -> 1 -> 12 -> 6 -> 4 -> 8 -> 10, средна вредност=6
Втора листа по префрлање: 1 -> 4 -> 5
Прва листа по префрлање: 12 -> 6 -> 8 -> 10
*/

import java.util.*;
import java.io.*;

class SLLNode<E> {
    protected E element;
    protected SLLNode<E> succ;

    public SLLNode(E elem, SLLNode<E> succ) {
        this.element = elem;
        this.succ = succ;
    }

    @Override
    public String toString() {
        return element.toString();
    }
}

class SLL<E> {

    private SLLNode<E> first;

    public SLL() {
        // Construct an empty SLL
        this.first = null;
    }

    public void deleteList() {
        first = null;
    }

    public int length() {
        int ret;
        if (first != null) {
            SLLNode<E> tmp = first;
            ret = 1;
            while (tmp.succ != null) {
                tmp = tmp.succ;
                ret++;
            }
            return ret;
        } else {
            return 0;
        }

    }

    @Override
    public String toString() {
        String ret = new String();
        if (first != null) {
            SLLNode<E> tmp = first;
            ret += tmp + " ";
            while (tmp.succ != null) {
                tmp = tmp.succ;
                ret += tmp + " ";
            }
        } else {
            ret = "Prazna lista!!!";
        }
        return ret;
    }

    public void insertFirst(E o) {
        SLLNode<E> ins = new SLLNode<E>(o, first);
        first = ins;
    }

    public void insertAfter(E o, SLLNode<E> node) {
        if (node != null) {
            SLLNode<E> ins = new SLLNode<E>(o, node.succ);
            node.succ = ins;
        } else {
            System.out.println("Dadenot jazol e null");
        }
    }

    public void insertBefore(E o, SLLNode<E> before) {

        if (first != null) {
            SLLNode<E> tmp = first;
            if (first == before) {
                this.insertFirst(o);
                return;
            }
            //ako first!=before
            while (tmp.succ != before) {
                tmp = tmp.succ;
            }
            if (tmp.succ == before) {
                SLLNode<E> ins = new SLLNode<E>(o, before);
                tmp.succ = ins;
            } else {
                System.out.println("Elementot ne postoi vo listata");
            }
        } else {
            System.out.println("Listata e prazna");
        }
    }

    public void insertLast(E o) {
        if (first != null) {
            SLLNode<E> tmp = first;
            while (tmp.succ != null) {
                tmp = tmp.succ;
            }
            SLLNode<E> ins = new SLLNode<E>(o, null);
            tmp.succ = ins;
        } else {
            insertFirst(o);
        }
    }

    public E deleteFirst() {
        if (first != null) {
            SLLNode<E> tmp = first;
            first = first.succ;
            return tmp.element;
        } else {
            System.out.println("Listata e prazna");
            return null;
        }
    }

    public E delete(SLLNode<E> node) {
        if (first != null) {
            SLLNode<E> tmp = first;
            if (first == node) {
                return this.deleteFirst();
            }
            while (tmp.succ != node&&tmp.succ.succ != null) {
                tmp = tmp.succ;
            }
            if (tmp.succ == node) {
                tmp.succ = tmp.succ.succ;
                return node.element;
            } else {
                System.out.println("Elementot ne postoi vo listata");
                return null;
            }
        } else {
            System.out.println("Listata e prazna");
            return null;
        }

    }

    public SLLNode<E> getFirst() {
        return first;
    }

    public SLLNode<E> find(E o) {
        if (first != null) {
            SLLNode<E> tmp = first;

            while (tmp.element != o && tmp.succ != null) {
                tmp = tmp.succ;
            }
            if (tmp.element == o) {
                return tmp;
            } else {
                System.out.println("Elementot ne postoi vo listata");
            }
        } else {
            System.out.println("Listata e prazna");
        }
        return first;
    }

    public Iterator<E> iterator() {
        // Return an iterator that visits all elements of this list, in left-to-right order.
        return new LRIterator<E>();
    }

    // //////////Inner class ////////////
    private class LRIterator<E> implements Iterator<E> {

        private SLLNode<E> place, curr;

        private LRIterator() {
            place = (SLLNode<E>) first;
            curr = null;
        }

        public boolean hasNext() {
            return (place != null);
        }

        public E next() {
            if (place == null) {
                throw new NoSuchElementException();
            }
            E nextElem = place.element;
            curr = place;
            place = place.succ;
            return nextElem;
        }

        public void remove() {
            //Not implemented
        }
    }

    public void mirror() {
        if (first != null) {
            //m=nextsucc, p=tmp,q=next
            SLLNode<E> tmp = first;
            SLLNode<E> newsucc = null;
            SLLNode<E> next;

            while (tmp != null) {
                next = tmp.succ;
                tmp.succ = newsucc;
                newsucc = tmp;
                tmp = next;
            }
            first = newsucc;
        }

    }

    public void merge(SLL<E> in) {
        if (first != null) {
            SLLNode<E> tmp = first;
            while (tmp.succ != null) {
                tmp = tmp.succ;
            }
            tmp.succ = in.getFirst();
        } else {
            first = in.getFirst();
        }
    }
}

public class PodeliSLL {
    public static SLL<Integer> sortLista(SLL<Integer> lista) {

        for(int i=0;i<lista.length();i++) {
            SLLNode<Integer> dvizi = lista.getFirst();
            while(dvizi!=null) {
                if(dvizi.succ!=null) {
                    if(dvizi.element<dvizi.succ.element) {
                        int tmp = dvizi.element;
                        dvizi.element=dvizi.succ.element;
                        dvizi.succ.element=tmp;
                    }
                    dvizi=dvizi.succ;
                }
                else {
                    break;
                }
            }
        }
        return lista;
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        SLL<Integer> lista = new SLL<Integer>();
        SLL<Integer> vtora = new SLL<Integer>();


        for(int i=0;i<n;i++) {
            lista.insertLast(Integer.parseInt(in.readLine()));
        }

        int s = Integer.parseInt(in.readLine());

        SLLNode<Integer> dvizi = lista.getFirst();


        while(dvizi!=null) {
            if(dvizi.element<s) {
                if(dvizi==lista.getFirst()) {
                    vtora.insertLast(dvizi.element);
                    lista.deleteFirst();
                    dvizi=lista.getFirst();
                }
                else {
                    SLLNode<Integer> dviziNazad=lista.getFirst();
                    while(dviziNazad.succ!=dvizi) {
                        dviziNazad=dviziNazad.succ;
                    }
                    dviziNazad.succ=dvizi.succ;
                    vtora.insertLast(dvizi.element);
                    dvizi=dvizi.succ;
                }
            }
            else {
                dvizi=dvizi.succ;
            }
        }

        System.out.println("PRVA LISTA PO PREFRLANJE: "+lista.toString());
        System.out.println("VTORA LISTA PO PREFRLANJE: "+sortLista(vtora).toString());
    }

}