[ADS/АПС] Lab 1.2: Join lists / Спој листи

/*
Join lists Problem 2 (0 / 0)

For given two single linked lists with integers sorted in ascending order, join them in a sorted single linked list in ascending order. Duplicate nodes should be deleted.

The first line in the input gives the first list node number, then in the second line there are the node numbers in the first list. The third line gives the second list node number, and in the end the forth line gives the numbers from the second list. The output prints the node numbers of the resulting list.

Class (Java): SLLJoinLists

Note: Create data structure single linked list and use it in this problem.
*/

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

class SLLNode<E> {
    public E elem;
    public SLLNode<E> succ;

    public SLLNode() {
        this.elem = null;
        this.succ = null;
    }

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

class SLL<E extends Comparable <E>> {
    private SLLNode<E> first;

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

    public SLL(SLLNode<E> first) {
        this.first = first;
    }

    public void insertFirst(E elem) {
        SLLNode<E> newNode = new SLLNode<E>(elem, null);
        if(this.first == null) this.first = newNode;
        else {
            newNode.succ = this.first;
            this.first = newNode;
        }
    }

    public void insertLast(E elem) {
        if(this.first == null) {
            insertFirst(elem);
            return;
        }
        SLLNode<E> curr = this.first;
        while(curr.succ != null) {
            curr = curr.succ;
        }
        SLLNode<E> newNode = new SLLNode<E>(elem, null);
        curr.succ = newNode;
    }

    public Iterator<E> iterator() {
        return new LRIterator<E>();
    }

    private class LRIterator<E> implements Iterator<E> {
        private SLLNode<E> place;

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

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

        public E next() {
            if(place == null)
                throw new NoSuchElementException();
            E nextElement = place.elem;
            place = place.succ;
            return nextElement;
        }
    }

    public void deleteSuccNode(SLLNode<E> node) {
        if(first == null || node.succ == null) return;
        node.succ = node.succ.succ;
    }

    public SLL<E> removeDuplicates(SLL<E> lista) {
        SLLNode<E> curr = lista.first;
        while(curr.succ != null) {
            if(curr.elem.compareTo(curr.succ.elem) == 0) {
                deleteSuccNode(curr);
            } else curr = curr.succ;
        }
        return lista;
    }

    public SLL<E> joinLists(SLL<E> lista) {
        SLL<E> finalList = new SLL<E>();
        SLLNode<E> curr1 = this.first;
        SLLNode<E> curr2 = lista.first;

        while(curr1 != null && curr2 != null) {
            if(curr1.elem.compareTo(curr2.elem) < 0) {
                finalList.insertLast(curr1.elem);
                curr1 = curr1.succ;
            } else {
                finalList.insertLast(curr2.elem);
                curr2 = curr2.succ;
            }
        }

        while(curr1 != null) {
            finalList.insertLast(curr1.elem);
            curr1 = curr1.succ;
        }

        while(curr2 != null) {
            finalList.insertLast(curr2.elem);
            curr2 = curr2.succ;
        }

        return removeDuplicates(finalList);
    }
}


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

        spoeni = lista1.joinLists(lista2);
        Iterator<Integer> it = spoeni.iterator();
        while (it.hasNext()) {
            System.out.print(it.next());
            if(it.hasNext())
                System.out.print(" ");
        }
        System.out.println();
    }
}