[ADS/АПС] Lab 1.3: Special Join List / Спој листи наизменичн

/*
Given two single linked lists with integer nodes, join them in a resulting single linked list in a way that alternatively adds at first the first two nodes from the first list, then the first two from the second, then next two from the first list, and then the second two from the second list, etc. The nodes that remain should be added at the end, at first from the first list, then the remaining from the second list.

In the first line from the input the numbers from the first list are given, and in the second line the numbers from the second list. The numbers from the resulting list should be printed at the output.

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> joinLists(SLL<E> lista) {
        SLL<E> finalList = new SLL<E>();
        SLLNode<E> curr1 = this.first;
        SLLNode<E> curr2 = lista.first;

        boolean flag = true;
        while(curr1 != null&&curr2 != null) {
            if(flag) {
                finalList.insertLast(curr1.elem);
                curr1 = curr1.succ;
                if(curr1 != null) {
                    finalList.insertLast(curr1.elem);
                    curr1 = curr1.succ;
                }
            } else {
                finalList.insertLast(curr2.elem);
                curr2 = curr2.succ;
                if(curr2 != null) {
                    finalList.insertLast(curr2.elem);
                    curr2 = curr2.succ;
                }
            }
            flag = !flag;
        }

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

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

        return finalList;
    }
}


public class SpecialSLLJoin {


    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();

    }
}