3 ms·
The list-cycle problem is from Knuth, not Design Patterns.
by timr 18y ago
The list-cycle problem is from Knuth, not Design Patterns.
- eru 18y agoOr any other basic text. SICP has it, too. And they have exactly the same follow up questiof of "reduce the space usage from O(n) to O(1)", too. (Incidentally a related method is know as "pollard's rho" and used to factor integers.)
- gms 18y agoCan you explain how Pollard can be used to find cycles in a linked list?
- eru 18y agoPlease have a look at http://en.wikipedia.org/wiki/Pollard_rho http://en.wikipedia.org/wiki/Pollard_rho "The rho algorithm is based on Floyd's cycle-finding algorithm [...]" (which can be found at http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoise_and_hare http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorit...)