Fast & Slow Pointers, Gaps and Merging

You can't ask a linked list for its length or its middle, but two pointers moving at different speeds answer both in one pass with O(1) space.

Fast & slow. slow moves one step, fast moves two. When fast reaches the end, slow has covered half the distance, so it's at the middle:

1 -> 2 -> 3 -> 4 -> 5
s,f
     s    f
          s         f   (fast.next is None: stop)

With an even length there are two middles. The loop while fast and fast.next lands on the second one; while fast.next and fast.next.next lands on the first (handy when you want to split a list in half).

Cycle detection (Floyd's tortoise and hare). If some node's next points back into the list, a plain walk never ends. Run fast & slow instead:

• No cycle: fast hits None. Done, False.
• Cycle: both pointers end up circling. Each step fast gains exactly one node on slow, so the gap between them shrinks by 1 until it's 0: they meet. Compare nodes with is, not values.

Bonus: to find where the cycle starts, put one pointer back at head after they meet and move both one step at a time; they meet again at the cycle's entrance.

A fixed gap: the nth node from the end. Start two pointers together, move fast ahead n steps, then move both until fast hits the end. slow is now n nodes behind the end.

Start both at a dummy node and stop when fast.next is None: slow then sits just before the target, which is exactly where you need to be to delete it.

Merging. To merge two sorted lists, keep a tail that starts at a dummy; repeatedly attach the smaller front node and advance. When one list runs out, attach the rest of the other in one go.

Split, reverse, merge. Many "rearrange the list" problems are these three moves in a row: find the middle (fast & slow), cut the list there (slow.next = None), reverse the second half, then weave or compare the halves. Palindrome check and Reorder List both work this way.