nedoresena

Спој листи Problem 2 (5 / 5)
Дадени се две еднострано поврзани листи чии јазли содржат по еден природен број. Листите се сортирани во растечки редослед. Треба да се спојат двете листи во една така што резултантната листа да е сортирана. Сортирањето е подредување со слевање. Јазлите кои се јавуваат како дупликати (од иста листа или од различна) да се отстранат.

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

Име на класата (Java): SLLJoinLists

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

package probno;

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

/**
 *
 * @author Sandra
 */
public class SLLJoinLists<E extends Comparable<E>> {

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

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

        public E getElement() {
            return element;
        }
    }

    public static class SLL<E> {
        private SLLNode<E> first;

        public SLL() {
            this.first = null;
        }

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

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

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

        public SLL<E> joinLists(SLL<E> lista1, SLL<E> lista2){
            SLL<E> lista3 = new SLL<E>();
            SLLNode<E> jazol1 = lista1.getFirst(), jazol2 = lista2.getFirst();

            while(jazol1 != null && jazol2 != null){
                if(jazol1.element.compareTo(jazol2.element)<0){
                    lista3.insertLast(jazol1.element);
                    jazol1 = jazol1.succ;
                }
                else{
                    lista3.insertLast(jazol2.element);
                    jazol2 = jazol2.succ;
                }
            }
            if(jazol1!=null){
                while(jazol1!=null){
                    lista3.insertLast(jazol1.element);
                    jazol1 = jazol1.succ;
                }
            }
            if(jazol2!=null){
                while(jazol2!=null){
                    lista3.insertLast(jazol2.element);
                    jazol2 = jazol2.succ;
                }
            }
        return lista3;
    }




        public static void main(String[] args) throws IOException {

    BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

        String s = stdin.readLine();
        int N = Integer.parseInt(s);
    s = stdin.readLine();
        String[] pomniza = s.split(" ");

        SLL<Integer> lista1 = new SLL<Integer>();

            for (int i = 0; i < N; i++) {
            lista1.insertLast(Integer.parseInt(pomniza[i]));
        }

        s = stdin.readLine();
        pomniza = s.split(" ");

        SLL<Integer> lista2 = new SLL<Integer>();

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

        SLL<Integer> lista3 = new SLL<Integer>();
        lista3 = joinLists(lista1, lista2);
   }
}