Problem

Given head, the head of a linked list, determine if the linked list has a cycle in it.

Return true if there is a cycle in the linked list. Otherwise, return false.

Examples

Example 1

Input:  head = [0, 1, 3, 2, 4]
output: true
Explanation: Cycle starts at node 2

Example 2

Input:  head = [1, 2, 3, 4, 5, 6]
output: true
Explanation: Cycle starts at node 3

Solution

Method 1 - Using Hashing

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 next of current node points to any of the previously stored nodes in Hash then return true.

Method 2 - Visited Flag

This solution requires modifications to basic linked list data structure.  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 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.

Method 3 - Floyd’s Cycle-Finding Algorithm i.e. Using 2 Pointers

Floyd Cycle-Finding Algorithm

Method 4 - Floyd’s Cycle-finding Algorithm (modified by Richard Brent)

Richard Brent described an alternative cycle detection algorithm, which is pretty much like the hare and the tortoise [Floyd’s cycle] except that, the slow node here doesn’t move, but is later “teleported” to the position of the fast node at fixed intervals. The description is available here : http://www.siafoo.net/algorithm/11 Brent claims that his algorithm is 24 to 36 % faster than the Floyd’s cycle algorithm. O(n) time complexity, O(1) space complexity. (Courtesy)

public static boolean hasLoop(Node root) {
	if (root == null) return false;

	Node slow = root, fast = root;
	int taken = 0, limit = 2;

	while (slow.next != null && fast.next != null) {
		fast = fast.next;
		taken++;
		if (slow == fast) return true;

		if (taken == limit) {
			taken = 0;
			limit<<= 1; // equivalent to limit *= 2;
			slow = fast; // teleporting the turtle (to the hare's position)
		}
	}
	return false;
}

Method 5 - Reverse a List

If there are no requirements on using extra memory and keeping the list in its original state very neat and simple approach can be uses. The idea is based on the fact that if you reverse the list which has loops you will end-up on the head node while if list doesn’t have loops you will stop at the tail.

public bool hasLoop(Node head) {
	Node first = null;
	Node second = null;
	Node tmp = head;

	while (tmp) {
		first = second;
		second = tmp;
		tmp = tmp.Next;

		if (tmp == head)
			return true;

		second.Next = first;
	}

	return false;
}