Easy · Fast & Slow Pointers
Understand → Visualise → Practice.
You can't index into a linked list, so finding the middle seems to need two passes: one to count, one to walk.
Move one pointer one node at a time and another two nodes at a time. When the fast one runs out, the slow one is at the middle.
slow = fast = head.
slow += 1, fast += 2.
When fast or fast.next is null, return slow.
O(n) time, O(1) space, one pass.
With an even number of nodes there are two middles; this loop returns the second one.
Read the full guide first: Linked Lists.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.