Find Middle of Linked List — Fast/Slow Pointer

Implementation

Node findMiddle(Node head) {
  Node slow = head, fast = head;
  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

Two conventions

Even length → return 2nd of 2 middle (as above) OR 1st middle (change condition to fast.next.next != null). Interviews often specify.

Used in

Split list for merge sort. Palindrome check (reverse 2nd half, compare). Delete middle.

Length-first alternative

Walk once for length N, walk N/2 for middle. Same complexity, twice the walks.