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.)
Sol: 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.
However , this may not be the best solution if the loop is very long as we ll have to iterate with in the loop many times. So, a better approach would be to associate a variable with each node and change or set its value once the node is encountered. So If we encounter a node whose variable value has already been set, that means we ve already traversed that node and thus be sure that loop exists.
No comments:
Post a Comment