Q. How to find middle element of singly linked list in one pass?

Ans: 

1. You have head (and  tail, which is not required)

2.  Take two pointers tmp1, tmp2 and initialize them to head

3. Iterate through the list, increment tmp1 in each iteration and increment tmp2 after every 2nd interation

4. When tmp1 reaches end of list, tmp2 should have reached middle element of the list

package cs.iit.edu.ds.question;

public class DSQuestions {

    public static void main(String args[]){

        SLL ll = new SLL();

        ll.addToTail(10);

        ll.addToTail(20);

        ll.addToTail(30);

        ll.addToTail(40);

        ll.addToTail(50);

        ll.addToTail(40);

        ll.addToTail(50);

        ll.addToHead(11);

        ll.addToHead(12);

        ll.addToHead(13);

        ll.addToHead(14);

        ll.printList();

        ll.findMiddle();

        }

}

class Node{

        Node next;

        int val;

        public Node(){

                next = null;

        }

        public Node(int n){

                val = n;

                next = null;

        }

        

        public Node(Node ptr, int n){

                next = ptr;

                val = n;

        }

}

class SLL{

        Node head = null;

        Node tail = null;

        void addToHead(int n){

                head = new Node(head, n);

                if(tail == null){

                        tail = head;

                }

        }

        public void findMiddle() {

                Node tmp1 = head;

                Node tmp2 = head;

                int i = 0;

                for(;tmp1 != null; tmp1 = tmp1.next){

                        i ++;

                                if( i == 2){

                                        i = 0;

                                        tmp2 = tmp2.next;

                                }

               }

                System.out.println("Middle element is : "+tmp2.val);

        }

        void addToTail(int n){

                if(tail == null){

                        tail = new Node(n);

                }

                tail.next = new Node(n);

                tail = tail.next;

                if(head == null){

                        head = tail;

                }

        }

        

        void printList(){

                for(Node tmp = head; tmp != null; tmp = tmp.next){

                        System.out.print(tmp.val +" --> ");

                }

                System.out.println();

        }

}

Output:

14 --> 13 --> 12 --> 11 --> 10 --> 20 --> 30 --> 40 --> 50 --> 40 --> 50 --> 

Middle element is : 20