Linked Lists
Two pointers at different speeds
One pointer moving twice as fast finds the middle, and catches anything going in circles.
Key idea
Finding the middle in one pass
You cannot index into a linked list, so finding the middle looks like it needs two passes: one to count, one to walk halfway.
It does not. Move one pointer one step at a time and another two steps at a time. When the fast one reaches the end, the slow one has covered exactly half the distance and is standing on the middle.
Gotcha
Which middle you get depends on the loop condition
With an even number of nodes there are two middles, and the condition decides which one you land on. The version above returns the second of the two, the 3 in a four-node list.
Changing the condition to while fast.next and fast.next.next returns the first middle instead. Problems care about this. Splitting a list into halves usually wants the node before the second half, which is the first middle.
Decide which one you need, then pick the condition. Do not adjust it until the tests pass, because both versions are correct for different questions and you will not know which you ended up with.
Edge cases
Both parts of the guard are load-bearing
while fast and fast.next checks two things. fast covers the case where fast has landed exactly on the end, and fast.next covers the case where it is one before the end and about to jump two.
Dropping either one raises AttributeError on None for lists of a particular parity, which is why a bug here shows up on even-length lists but not odd ones, or the reverse. Test both.
Why it works
Why a fast pointer catches a cycle
If the list loops back on itself, the fast pointer enters the loop first and then goes round it. The slow pointer arrives later and also goes round.
Once both are inside, the fast pointer gains exactly one position on the slow pointer per step. A gap that shrinks by one every step and can never skip a value must eventually reach zero, so they meet. If there is no cycle, the fast pointer simply reaches the end.
That one-per-step argument is the whole proof, and it is why the speeds are one and two rather than any other pair. A faster pointer would close the gap by more than one per step and could jump over the slow pointer without ever landing on it.
Nothing about that argument needs a linked list. Below, two runners sit on six numbered positions arranged in a loop, and the printed value is the distance the fast one still has to close.
Gotcha
Compare identity, not value
On a real list the two pointers hold nodes rather than numbers, so the test for whether they have met is slow is fast, which asks whether the two names refer to the same node object.
slow == fast would compare with whatever equality the class defines, which for a plain node class is also identity, but stops being so the moment anyone adds an __eq__.
More importantly, two different nodes can hold the same value, and comparing values would report a meeting that never happened. Use is for node comparison throughout this unit.
Cost
Against the obvious alternative
Storing every visited node in a set also detects a cycle, in O(n) time and O(n) space. The two-pointer version is O(n) time and O(1) space.
Give the set version first if it comes to you faster; it is correct and easy to explain. The constant-space version is the follow-up they are usually waiting for, and the gap-shrinks-by-one argument is what makes it more than a memorized trick.
Trace fast and slow
Run the middle-finding loop on a five-node list holding 1 through 5. For each pass give the values slow and fast are standing on after the step, writing None when a pointer has run off the end.
This activity type is not wired up yet.
Linked List Cycle
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.