/**assuming list has no loop * two ideas: * 1.count number of nodes in linked list, then return the middle ceiling(n/2) * 2. have two pointers to move towards end of list. one faster moving 2 steps each time, meanwhile, slower moves 1 step each time * when fast pointer moves to end of list, slower points to middle of list * @param aList * @return */ public static ListNode getMiddleOfLinkedList(ListNode aList){ if (aList== null) return null; ListNode p1 = aList, p2=aList; //only move p2 when it has chance to move two steps while(p2!=null && p2.next!=null && p2.next.next!= null){ p2=p2.next.next; p1=p1.next; } //when p2 can no longer move, it either has no following node or just one node, //p1 already points to correct position if middle is defined as last element in left part when number of nodes is odd return p1; }