This pseudo-code holds for a Single Linked list:

1. init two pointers(p1,p2) at head of the linked list

2. p2 traverses twice as fast as p1

3. For each iteration p1=p1.next and p2=p2.next.next;

4. if p2==null or p2.next=null return middle element = p1

5. Repeat Step 2

6. return p1

This pseudo-code holds for adding node after getting p1 as median

if(p1==null)`enter code here`

add node at p1

else

{

store next node of p1 in temp

add new node at p1.next

add temp at p1.next.next

}

Complexity : O(n)+1