Почему это работает
- Пусть a — шагов от головы до начала петли, а L — длина петли. При встрече fast прошёл вдвое больше slow, и лишнее — это целые круги: slow прошёл кратное L.
- Значит, от места встречи ещё a шагов приведут slow в точку a + (кратное L), то есть в начало петли. Указатель с головы придёт туда за те же a шагов.
- Во втором цикле оба идут по одному шагу, поэтому впервые сходятся ровно в начале петли, не раньше: до него один ещё на хвосте, а другой на петле.
Сложность
Время O(n): первый цикл делает меньше n раундов, как в Linked List Cycle, а второй ровно a, длину хвоста. Память O(1): два указателя и никакого множества посещённых узлов.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗