Exercise_3.java

//Time Complexity - O(n)
class LinkedList {

    Node head; // head of linked list

    /* Linked list node */
    class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    /* Function to print middle of linked list */
    void printMiddle() {

        Node sp = head;
        Node fp = head;

        if (head != null) {
            while (fp != null && fp.next != null) {
                fp = fp.next.next;
                sp = sp.next;
            }

            System.out.println("Middle element: " + sp.data);
        }
    }

    public void push(int new_data) {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }

    public void printList() {
        Node tnode = head;
        while (tnode != null) {
            System.out.print(tnode.data + "->");
            tnode = tnode.next;
        }
        System.out.println("NULL");
    }

}

class Main {
    public static void main(String[] args) {

        LinkedList llist = new LinkedList();
        for (int i = 15; i > 0; --i) {
            llist.push(i);
            llist.printList();
            llist.printMiddle();
        }
    }
}