A linked list may loop: the last node's next can point back to some earlier node instead of None. Write detect_cycle(head) that returns the node where the cycle begins (the first node you visit twice when walking from head), or None if the list ends normally.
The list has up to 100,000 nodes. Don't modify the list. Aim for O(n) time and O(1) extra memory: a set of visited nodes is accepted by the tests, but try to do without it.
6 -> 1 -> 8 -> 2 -> (back to 1) returns the node with value 1
6 -> 1 -> 8 -> (back to 6) returns the head node
6 -> 1 -> 8 -> None returns None
5 -> (back to 5) returns that single node
Return the node object itself, not its value or index; values may repeat.
Show hint
Two pointers moving through the list at different speeds must meet inside the cycle if there is one. Then think about the distances: how far is the meeting point from the cycle's entry, compared with how far head is from it?