# Loop Detection

Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.

Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.

```
Input: A -> B -> C -> D -> E -> C // C is the same as earlier
Output: C
```

## Link here to the repo to solve the problem

👉## 👌 Tips

There are really two parts to this problem. First, detect if the linked list has a loop. Second, figure out where the loop starts.

To identify if there's a cycle, try the "runner" approach described at the start of this chapter. Have one pointer move faster than the other.

You can use two pointers, one moving twice as fast as the other. If there is a cycle, the two pointers will collide. They will land at the same location at the same time.Where do they land? Why there?

If you haven't identified the pattern of where the two pointers start, try this: Use the linked list 1->2->3->4->5->6->7->8->9->?, where the? links to another node. Try making the? the first node (that is, the 9 points to the 1 such that the entire linked list is a loop). Then make the? the node 2. Then the node 3. Then the node 4. What is the pattern? Can you explain why this happens?

## 👊 Solution 1

In this solution I iterate through the LinkedList while adding each unique HashCode to a HashSet. If the HashCode Repeats I break the iteration loop and return that node, otherwise if I iterated through the whole list I just return null.

The runtime will be O(N) and the space is(1) due to the HashMap

```
public static SingleLinkedListNode loopDetectionHashMap(SingleLinkedListNode head) {
HashSet<Integer> map = new HashSet<>();
while (head.next != null) {
if (map.contains(head.hashCode())) break;
map.add(head.hashCode());
head = head.next;
}
return head.next != null ? head : null;
}
```

Lets see if we can find a way to optimise the space:

## 👊 Solution 2

If you've followed the tips and manually drew the lists with the runner approach, you will realise that at some point both the slow and fast runner will eventually hit the node which is the start of the list. When this happens we can simply return that node. If the fast runner ends it means that it was not a circular list.

```
public static SingleLinkedListNode loopDetection(SingleLinkedListNode head) {
SingleLinkedListNode fast = head.next.next;
SingleLinkedListNode slow = head.next;
while (fast.next!= null && fast.next.next != null) {
if (fast.hashCode() == slow.hashCode()) {
return slow;
}
slow = slow.next;
fast = fast.next.next;
}
return null;
}
```

*Question borrowed from “Cracking the coding interview”*