public class LinkedList <Т>{
    Node head;

    void addElementAtBegining(Т el) {
        Node n = new Node(el);
        n.next = head;
        head = n;
    }

    void addElementAtEnd(Т el) {
        Node n = new Node(el);

        Node current = head;
        while(current.next != null) {
            current = current.next;
        }
        current.next = n;
    }

    void addElementWithIndex(int index, Т el) {
        if(index > this.size()-1){
            return;
        }
        int counter = 0;
        Node n = new Node(el);

        Node current = head;

        while(counter+1 != index) {
            current = current.next;
            counter++;

        }
        n.next = current.next;
        current.next = n;

    }

    void deleteWithIndex(int index) {
        int counter = 0;

        Node current = head;

        while(counter+1 != index) {
            current = current.next;
            counter++;

        }
        current.next = current.next.next;
    }

    Node sortedMerge(Node a, Node b)
    {
        Node result = null;

        if (a == null)
            return b;
        if (b == null)
            return a;

        if ((int)a.data <= (int)b.data) {
            result = a;
            result.next = sortedMerge(a.next, b);
        }
        else {
            result = b;
            result.next = sortedMerge(a, b.next);
        }
        return result;
    }

    Node mergeSort(Node h)
    {
        if (h == null || h.next == null) {
            return h;
        }

        Node middle = getMiddle(h);
        Node nextofmiddle = middle.next;

        middle.next = null;

        Node left = mergeSort(h);

        Node right = mergeSort(nextofmiddle);

        Node sortedlist = sortedMerge(left, right);
        return sortedlist;
    }

    public static Node getMiddle(Node head)
    {
        if (head == null)
            return head;

        Node slow = head, fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    LinkedList[] split() {
        LinkedList[] splittedArr = new LinkedList[2];
        int counter = 0;
        Node current = head;
        splittedArr[0] = new LinkedList();
        splittedArr[0].addElementAtBegining(current.data);

        while(counter+1 != this.size()/2) {
            splittedArr[0].addElementAtEnd(current.next.data);
            current = current.next;
            counter++;
        }
        current = current.next;
        splittedArr[1] = new LinkedList();
        splittedArr[1].addElementAtBegining(current.data);
        while(counter+2 != this.size()) {
            splittedArr[1].addElementAtEnd(current.next.data);
            current = current.next;
            counter++;
        }
        return splittedArr;

    }
    int size() {
        int counter = 1;
        Node current = head;
        while(current.next != null) {
            current = current.next;
            counter++;
        }
        return counter;
    }
    public void print() {
        Node current = head;
        while(current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}