ProAnswers.org

How to find a loop in a linked list

Given a linked list, how can i determine if there is a loop in it?

Traverse through the nodes of the linked list. Color the node that you traverse. While traversing, if you reach a colored node before reaching the end, it means the linked-list contains a loop otherwise it doesn’t

Time Complexity: O(n)