Detection of Loop in a Linked List
source link: https://www.geeksforgeeks.org/videos/detection-of-loop-in-a-linked-list/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Detection of Loop in a Linked List
- 10 Views
- 10/06/2022
Traverse the list one by one and keep putting the node addresses in a Hash Table. At any point, if NULL is reached then return false, and if the next of the current nodes points to any of the previously stored nodes in Hash then return true. Have a visited flag with each node. Traverse the linked list and keep marking visited nodes. If you see a visited node again then there is a loop. This solution works in O(n) but requires additional information with each node. A variation of this solution that doesn’t require modification to basic data structure can be implemented using a hash, just store the addresses of visited nodes in a hash and if you see an address that already exists in hash then there is a loop.
Detection of Loop in a Linked List : https://www.geeksforgeeks.org/detect-loop-in-a-linked-list/
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK