Check the Entire List So Far O(n^2) time complexity For each node, assume that the portion of the list examined so for has no loops and check to see if the next node creates a loop by iterating again over the entire list up to that point. // Inefficient solution function boolean hasLoop(Node startNode){ Node currentNode = startNode.next(); int i=0; do { Node checkNode = startNode; int j=0; do { if (checkNode == currentNode) return true; j++; } while (j

O(n) time complexity If you reverse the list, and remember the inital node, you will know that there is a cycle if you get back to the first node. While efficient, this solution changes the list. Reversing the list twice would put the list back in its initial state, however this solution is not appropriate for multi-threaded applications. In some cases there may not be a way to modify nodes. Since changing the nodes is not needed to get the answer, this solution is not recommended. // Solution modifies the list function boolean hasLoop(Node startNode){ Node previousNode = null; Node currentNode = startNode; Node nextNode; if (!currentNode.next()) return false; while(currentNode){ nextNode = currentNode.next(); currentNode.setNext(previousNode); previousNode = currentNode; currentNode = nextNode; } return (previousNode == startNode); }

Use Memory Allocation Information O(n) time complexity in the amount of memory on the computer Some programming languages allow you to see meta information about each node -- the memory address at which it is allocated. Because each node has a unique numeric address, it is possible to use this information to detect cycles. For this algorithm, keep track of the minimum memory address seen, the maximum memory address seen, and the number of nodes seen. If more nodes have been seen than can fit in the address space then some node must have been seen twice and there is a cycle. // Depends on size of available computer memory rather than size of list function boolean hasLoop(Node startNode){ Node currentNode = startNode; int minAddress, int maxAddress = ¤tNode; int nodesSeen = 0; while(currentNode = currentNode.next()){ nodesSeen++; if (¤tNode maxAddress) maxAddress = ¤tNode; if (maxAddress - minAddress < nodesSeen) return true; } return false; }

Best Solutions Catch Larger and Larger Loops O(n) time complexity Always store some node to check. Occasionally reset this node to avoid the "Detect Only Full Loops" problem. When resetting it, double the amount of time before resetting it again. // Good solution function boolean hasLoop(Node startNode){ Node currentNode = startNode; Node checkNode = null; int since = 0; int sinceScale = 2; do { if (checkNode == currentNode) return true; if (since >= sinceScale){ checkNode = currentNode; since = 0; sinceScale = 2*sinceScale; } since++; } while (currentNode = currentNode.next()); return false; } This solution is O(n) because sinceScale grows linearly with the number of calls to next(). Once sinceScale is greater than the size of the loop, another n calls to next() may be required to detect the loop. This solution requires up to 3 traversals of the list. This solution was devised by Stephen Ostermiller and proven O(n) by Daniel Martin. Catch Loops in Two Passes O(n) time complexity Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator. // Best solution function boolean hasLoop(Node startNode){ Node slowNode = Node fastNode1 = Node fastNode2 = startNode; while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){ if (slowNode == fastNode1 || slowNode == fastNode2) return true; slowNode = slowNode.next(); } return false; } This solution is "Floyd's Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm".