Linked List - find an answer
Puzzle Question:
how does one find a loop in a singly linked list in O(n) time using constant memory? you cannot modify the list in any way (and constant memory means the amount of memory required for the solution cannot be a function of n.)
Level of Toughness:
Intermediate
One way to detect a loop is
One way to detect a loop is to iterate over the list with 2 pointers at the same time where one is iterating at double speed. If the 2 pointers are ever equal after they iterate once and before they both reach an end, there's a loop.
You may like to check linked
You may like to check linked list loop solution.