How do you find the middle node of a linked list?

Use the slow and fast pointer technique. Start both at the head. Move slow one step and fast two steps. When fast reaches the end or the node before the end, slow is at the middle. For even-length lists, this gives the second of the two middle nodes. This runs in O of n time and O of one space, which is better than first counting the length and then traversing to the midpoint because it requires only one pass. Finding the middle is used as a subroutine in merge sort of linked lists and in checking if a linked list is a palindrome.