1. Midpoint of the LL #

Created Saturday 18 January 2020

Remember the middle element is floor((length-1)/2)

• For uni or empty return head.
• Make two pointers travx and trav2x. Both initialized as head.
• while(travx->next!=NULL and trav2x->next->next!=NULL) // no other way, we will miss the even case.

travx = travx -> next; trav2x = trav2x -> next -> next; // we don’t need to check the case where trav2x == NULL, i.e we have never made that move.

• When the loop ends. We are at the list of the first element. Stop operations.
  1. For odd sized list. We are at the middle element;
  2. For even size. We are at the element that is.

Length is not necessary to be calculated for getting the middle element. Proof: Intuition and PMI