## We have a singly-linked list and want to check if it contains a cycle

The difference between a regular LinkedList and a LinkedList with a Loop is that, There are two nodes in a `LinkedList` with a loop whose next pointers are the same. In a regular single `LinkedList` (without a loop) each node’s next pointer is unique. So the repeatation of next pointer in a `LinkedList `is actually indication of a loop. Following figure is an example of a `LinkedList` with a Loop.

Brute-Force Approach: One simple and brute force approach of solving this problem is , start with the first node and check whether there is any node whose next pointer is the current node’s address. If there is a node whose next is same as the current node’s address then that indicates that some other node is pointing to the current node resulting a loop in the linked list. Continue this process for all the nodes in the linked list, now there are 2 possible outcome:

1. You reaches `NULL` or the end of the linked list. That means there are no loop in this linked list.
2. You will identify a loop in the linked list by following the above approach.

Can we do better to solve the problem? Can we use a `HashTable` to solve the problem?

Using HashTable: The following algorithm using a `HashTable` can be used to solve the problem.

1. Traverse the LinkedList node one by one.
2. Check whether the node’s address is available in the HashTable or not.
3. If the node’s address is already available in the hash table, that indicates we have already visited the node earlier and which is a indicator of a loop.
4. If the node’s address is not present in the hash table, then add it to the hash table.
5. Continue this process until the reach the end of the linked list or we find a loop.

Time complexity of this algorithm is O(n) for traversing the linked list. And space complexity is O(n) for creating the hash table.

Can we still do better to solve the problem? Yes, we can solve this problem with Time Complexity of O(n)and  without extra memory. The problem can be solved using Floyd cycle detection algorithm. It uses two pointers moving at different speed in the linked list. And both the pointers are expected to meet if there is a loop in the linked list. Otherwise for a regular singly linked list (without a loop) the fast pointer will reaches to the end. Think of a tortoise and a hare running on a track, the faster running hare will catch up with the tortoise if they are running in a Loop. Let us implement the algorithm. Following is the `LinkedList `ADT we are going to use for the implementation.

`Node.java`

```package com.algo.linkedlist;

/**
* Created by ardas on 9/14/2018.
*/
public class Node {

int data;
Node next;

public Node(int data) {
this.data = data;
this.next = null;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return data == node.data && next == node.next;
}

public void print() {
System.out.print(this.data);
}
}```
`LinkedList.java`
```package com.algo.linkedlist;

/**
* Created by ardas on 9/14/2018.
*/

/**
* Create a Singly LinkedList of given size
*
* @param size Size of the LinkedList
*/

for (int i = 2; i <= size; i++) {
Node node = new Node(i);
tempNode.next = node;
tempNode = tempNode.next;
}
}

/**
* Create a LinkedList with a Loop
*
* @param size        Size of the LinkedList
* @param loopStartAt where the Loop Start
*/
public LinkedList(int size, int loopStartAt) {
for (int i = 2; i <= size; i++) {
Node node = new Node(i);
tempNode.next = node;
tempNode = tempNode.next;
}
for (int i = 1; i < loopStartAt; i++) {
loop = loop.next;
}
tempNode.next = loop;
}
}```

Now let us implement the Floyd cycle detection algorithm

```package com.algo.linkedlist;

/**
* Created by ardas on 9/18/2018.
*/
public class FindLoop {

/**
* Finding Loop using Floyd cycle detection algorithm
*
* @return
*/
while (fastPtr != null && fastPtr.next != null) {
fastPtr = fastPtr.next.next;
slowPtr = slowPtr.next;
if (fastPtr != null && fastPtr.equals(slowPtr)) {
return true;
}
}
return false;
}
}```

Let us Test the implementation by using 2 LinkedList. Where one linked list has a loop but the other don’t have any loop.

```LinkedList linkedListWithLoop = new LinkedList(10, 3);

Now if we apply the algorithm on these 2 linked list, then it will detect the loop for `linkedListWithLoop` but returns a false to the question `hasLoop?` for `linkedListWithOutLoop`

```public static void testCircularLinkedList() {
FindLoop findLoop = new FindLoop();
System.out.println("LinkedList has Loop by FloydCycleDetection: "
System.out.println("LinkedList has Loop by FloydCycleDetection: "

}```