Почему это работает
- random может смотреть вперёд, на узел, у которого копии ещё нет. Поэтому первый проход только делает копии, а второй связывает их, когда все копии уже есть.
- Словарь «старый узел → его копия» превращает каждую ссылку в один поиск: копия node.random — это copy[node.random], искать по списку не нужно.
- Каждая ссылка копии берётся из словаря, а в словаре только новые узлы, поэтому из копии нельзя попасть в старый список.
Сложность
Время O(n): два прохода по списку, каждый поиск в словаре — O(1). Память O(n): в словаре по записи на узел, не считая самой копии.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗