[APS] ISPITNA JUNI 2014

APS 13.06.2014:

Спои листи Problem 1 (0 / 0)
Дадени се две двострано поврзани листи чии што јазли содржат по еден природен број.
Од овие две листи треба да се креира нова двострано поврзана листа,
на тој начин што јазлите ќе се додаваат наизменично и тоа само оние со парни броеви
 (прв елемент од првата листа (ако е парен), последен од втората (ако е парен),
втор елемент од првата листа (ако е парен), претпоследен од втората (ако е парен) итн.).
Јазлите со парни броеви кои ќе останат треба да се додадат на крај во резултантната листа.
Потоа на резултантната листа се додаваат само преостанатите јазли со непарни елементи од
првата листа и преостанатите јазли со непарни елементи но во обратен редослед од втората листа.

Освен наведените три листи немате право на користење на дополнителни помошни листи.

Во првиот ред од влезот е даден бројот на јазли во првата листа, потоа во вториот ред се дадени
броевите од кои се составени јазлите по редослед во првата листа, па во третиот ред е даден
бројот на јазли во втората листа, и на крај во четвртиот ред броевите од кои се составени јазлите
по редослед во втората листа. На излез треба да се испечатат јазлите по редослед во
резултантната споена листа.

Забелешка: При реализација на задачите МОРА да се користат дадените структури,
а не да се користат помошни структури како низи или сл.

Делумно решение: Задачата се смета за делумно решена доколку се поминати 7 тест примери.

Име на класата: SpoiListi


Sample input
20
18 5 77 5 57 15 27 43 26 0 31 61 50 63 34 25 52 4 72 24
50
90 31 93 52 40 13 8 77 43 82 71 99 95 56 13 30 4 14 10 27 33 12 18 52 5 59 48 25 80 84 57 2 64 94 4 62 7 68 77 64 27 7 39 91 59 24 87 95 22 28
Sample output
18 28 22 24 26 0 64 50 68 34 62 4 52 94 4 64 72 2 24 84 80 48 52 18 12 10 14 4 30 56 82 8 40 52 90 5 77 5 57 15 27 43 31 61 63 25 95 87 59 91 39 7 27 77 7 57 25 59 5 33 27 13 95 99 71 43 77 13 93 31


=========================================================================================================================================
package mojsadsada;



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


class DLLNode<E> {
    protected E element;
    protected DLLNode<E> pred, succ;

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

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

class DLL<E> {
    private DLLNode<E> first, last;

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

    public void deleteList() {
        first = null;
        last = null;
    }

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

    }

    public void insertFirst(E o) {
        DLLNode<E> ins = new DLLNode<E>(o, null, first);
        if (first == null)
            last = ins;
        else
            first.pred = ins;
        first = ins;
    }

    public void insertLast(E o) {
        if (first == null)
            insertFirst(o);
        else {
            DLLNode<E> ins = new DLLNode<E>(o, last, null);
            last.succ = ins;
            last = ins;
        }
    }

    public void insertAfter(E o, DLLNode<E> after) {
        if (after == last) {
            insertLast(o);
            return;
        }
        DLLNode<E> ins = new DLLNode<E>(o, after, after.succ);
        after.succ.pred = ins;
        after.succ = ins;
    }

    public void insertBefore(E o, DLLNode<E> before) {
        if (before == first) {
            insertFirst(o);
            return;
        }
        DLLNode<E> ins = new DLLNode<E>(o, before.pred, before);
        before.pred.succ = ins;
        before.pred = ins;
    }

    public E deleteFirst() {
        if (first != null) {
            if (first.succ == null){
                last = null;
                first = null;
            }
            else{
                DLLNode<E> tmp = first;
                first = first.succ;
                first.pred = null;
                return tmp.element;
            }
        }
        return null;
    }

    public E deleteLast() {
        if (first != null) {
            if (first.succ == null)
                return deleteFirst();
            else {
                DLLNode<E> tmp = last;
                last = last.pred;
                last.succ = null;
                return tmp.element;
            }
        }
        // else throw Exception
        return null;
    }

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

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

    public DLLNode<E> getLast() {

        return last;
    }

}

class SpoiListi  {


    public static DLL<Integer> mergeLists(DLL<Integer> list1, DLL<Integer> list2){

        // 2 pokazuvaci, 1 zalapen za poceokt na 1, 2 za kraj na 2
        DLLNode<Integer> p1 = list1.getFirst();
        DLLNode<Integer> p2 = list2.getLast();
        DLL<Integer> rezz = new DLL<Integer>();

        // dodeka 2ta ne se nulevi
        while(p1 != null && p2 != null){
            if(p1.element % 2 == 0){
                rezz.insertLast(p1.element);
            }
            p1 = p1.succ;

            if(p2.element % 2 == 0){
                rezz.insertLast(p2.element);
            }
            p2 = p2.pred;

        }


        // ako 1 ne e null, dodavaj parni
        if(p1 != null){
            while(p1 != null){
                if(p1.element %2 == 0){
                    rezz.insertLast(p1.element);
                }
                p1 = p1.succ;
            }
        }
        // ako 2 ne e null dodavaj neparni
        if(p2 != null){
            while(p2 != null){
                if(p2.element % 2 == 0){
                    rezz.insertLast(p2.element);
                }
                p2 = p2.pred;
            }
        }

        // dodavaj ostala raja

        p1 = list1.getFirst();
        p2 = list2.getLast();
        while( p1 != null && p2 != null){

            if(p1.element % 2 != 0)
                    rezz.insertLast(p1.element);

            p1 = p1.succ;

            if(p2.element % 2 != 0)
                rezz.insertLast(p2.element);

            p2 = p2.pred;

        }

        // ako 1 ne e null, dodavaj parni
        if(p1 != null){
            while(p1 != null){
                if(p1.element %2 != 0){
                    rezz.insertLast(p1.element);
                }
                p1 = p1.succ;
            }
        }
        // ako 2 ne e null dodavaj neparni
        if(p2 != null){
            while(p2 != null){
                if(p2.element % 2 != 0){
                    rezz.insertLast(p2.element);
                }
                p2 = p2.pred;
            }
        }

        return rezz;

    }

    public static void main(String[] args) throws IOException {
        DLL<Integer> lista1 = new DLL<Integer>(), lista2 = new DLL<Integer>();
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        String s = stdin.readLine();
        int N = Integer.parseInt(s);
        s = stdin.readLine();
        String[] pomniza = s.split(" ");
        for (int i = 0; i < N; i++) {
            lista1.insertLast(Integer.parseInt(pomniza[i]));
        }

        s = stdin.readLine();
        N = Integer.parseInt(s);
        s = stdin.readLine();
        pomniza = s.split(" ");
        for (int i = 0; i < N; i++) {
            lista2.insertLast(Integer.parseInt(pomniza[i]));
        }

        //vasiot kod tuka!

        DLL<Integer> nova = mergeLists(lista1,lista2);
        DLLNode<Integer> p = nova.getFirst();
        while(p!= null){
            System.out.print(p.element + " ");
            p = p.succ;
        }

    }
}