LinkedList

//Class Node
public class Node {
    public int data;
    public Node next;

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

}


//Class LinkedList

public class LinkedList {

    Node head;


    public void push(int new_data){
        if(head==null){
            head=new Node(new_data);
            return;
        }

        Node newNode=new Node(new_data);
        newNode.next=head;
        head=newNode;
    }

    public int getCount(){
        if(head==null) return 0;

        Node temp=head;

        int count=0;

        while(temp!=null){

            //System.out.println(temp.data);
            count++;
            temp=temp.next;

        }

        return count;
    }

    //Bonus task
    public Node getMiddleNode() throws Exception{

        //Throw exception if the list is empty
        if(head==null) throw new Exception("The list is empty.");

        //If the list contains just one element (head), return that element
        if(head.next==null) return head;

        /*Initalize 2 'support' nodes that represent the pointers to elements of the list
        and which start at the first element of the list*/
        Node temp1=head;
        Node temp2=head;

        /*Move the temp1 node for 1 and temp2 for 2 places until temp2 is null
        or temp2 is the last element of the list. When temp2 comes to the end of the list, the
        temp1 node will be in the middle.
        */
        while(temp2!=null){
            if(temp2.next==null) return temp1;

            temp1=temp1.next;
            temp2=temp2.next.next;

        }

        return temp1;

    }

    public static void main(String[] args){

        LinkedList llist=new LinkedList();
        llist.push(1);
        llist.push(3);
        llist.push(1);
        llist.push(2);
        llist.push(1);


        System.out.println("Count of nodes is: "+ llist.getCount());

        //Bonus task
        try {
            Node node=llist.getMiddleNode();
            System.out.println("Middle node is: " +node.data);
        } catch (Exception ex) {
            System.out.println(ex.getMessage());
        }

    }


}