almost 6 years ago
Can anybody tell me the complexity of Floyd cycle detection algorithm in singly linked list with proof.
Floyd cycle detection algo used to detect the infinite loops inside lists, symlinks, state machines.
Make two pointer from starting of the list , increment one pointer by 1 and another by 2 on every iteration if both pointer meets it means there is loop.
If second pointer reaches at the end , it means there is no loop.
so complexity are O(n) time and O(1) space
Please go over following link: http://codingfreak.blogspot.com/2012/09/detecting-loop-in-singly-linked-list_22.html
I think this will help you in what you are looking.
hi Avish , please go over the following link====>
I hope this link is helpful. This explains the complete "Floyd's Cycle Detection Algorithm", also known as "Tortoise and Hare Algorithm".
It also has the complete pseudo code.
Starting with Chrome version 45, NPAPI is no longer supported for Google Chrome. For more information, see Chrome and NPAPI (blog.chromium.org).
Firefox and Microsoft Internet Explorer are recommended browsers for websites using java applets.
Chrome Version Support
Are you sure, you want to delete this comment?
Terms of Service
| © copyright 2020 FindNerd.com. All rights reserved.
Sign up using