[Java][АПС] - Спој листи

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

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

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

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

Sample input
3
2 3 5
1
3

Sample output
2 3 5

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.NoSuchElementException;


public class SpecialSLLJoin {
	private static SLL<Integer> specialJoin(SLL<Integer> lista1,SLL<Integer> lista2) {

		SLL<Integer> nova = new SLL<Integer>();
					SLLNode<Integer> tmp1 = lista1.getFirst();
					SLLNode<Integer> tmp2 = lista2.getFirst();

					if(tmp1!=null&&tmp1.succ!=null&&tmp2!=null&tmp2.succ!=null){
						while(tmp1.succ!=null&&tmp2.succ!=null){
							nova.insertLast(tmp1.element);
							nova.insertLast(tmp1.succ.element);

							nova.insertLast(tmp2.element);
							nova.insertLast(tmp2.succ.element);

							if(tmp1.succ.succ!=null){
							tmp1 = tmp1.succ.succ;} else {}
							if(tmp2.succ.succ!=null){
							tmp2 = tmp2.succ.succ;}else { }
						}
					}

					while(tmp1!=null){
						nova.insertLast(tmp1.element);
						tmp1 = tmp1.succ;
					}
					while(tmp2!=null){
						nova.insertLast(tmp2.element);
						tmp2 = tmp2.succ;
					}


					return nova;
			}
			public static void print(SLL<Integer> list){
				SLLNode<Integer> vrti = list.getFirst();
				for(int i = 0;i<list.length();i++){
					System.out.print(vrti.element + " ");
					vrti = vrti.succ;
				}
			}


	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>();
		SLL<Integer> lista2 = new SLL<Integer>();
		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(" ");
		SLL<Integer> spoeni = new SLL<Integer>();
		for (int i = 0; i < N; i++) {
			lista2.insertLast(Integer.parseInt(pomniza[i]));
		}

		spoeni = specialJoin(lista1,lista2);
		//System.out.println(spoeni.toString()+ " ");
		print(spoeni);
	}

	}



class SLLNode<E> {
	protected E element; // value
	protected SLLNode<E> succ; // link

	public SLLNode(E elem, SLLNode<E> succ) { // 1. value , 2.link
		this.element = elem; //value
		this.succ = succ; //link
	}

	@Override
	public String toString() {
		return element.toString(); // vo bukvi samo
	}
}



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> first) {
		if (first != null) {
			SLLNode<E> ins = new SLLNode<E>(o, first.succ);
			first.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();
		}
	}
}