# 2.8. Loop detection

> Given a linked list which might contain a loop, implement an algorithm that returns the node at the beginning of the loop, if one exists

* Input: A --> B --> C --> D --> E --> C (same C as earlier)
* Output: C

## First idea

Brute force idea would be O(n^2), or O(n) time and O(n) space, we need to somehow keep the nodes in memory. Even if we keep n in memory, we need to iterate. Not if we use hash table...

```java
public static LinkedListNode loop_detection(LinkedListNode head){
    Hashtable<LinkedListNode> nodes = new Hashtable<LinkedListNode>();
    while(head != null){
        if (nodes.containsKey(head)){
           return head;
        }
        nodes.put(head);
        head = head.next;
    }
    return null;
}
```

Should work... we're saving the node by reference. And it's O(n) time, O(n) space.

## Hint 1

> There are two parts to this problem, first detect if there's a loop, then find where the loop starts

We can't compare by reference, otherwise it'd be an infinite loop. Need to compare by data, and save `LinkedListNode` as value.

```java
public static LinkedListNode loop_detection(LinkedListNode head){
    Hashtable<Integer, LinkedListNode> nodes = new Hashtable<Integer, LinkedListNode>();
    while(head != null){
        if (nodes.containsKey(head.data)){
           return nodes.get(head.data); // return LinkedListNode stored in HashTable
        }
        nodes.put(head.data, head);
        head = head.next;
    }
    return null;
}
```

## Hint 2

> To identify if there's a cycle, try the runner approach, have one pointer move faster than the other.

But how much faster? we don't know how long/big the loop can be. Faster and faster? then we'd miss some values...

## Hint 3

> Have one pointer move double faster than the other, if there's a cycle, they will collide. They will land on the same location at the same time. Where do they land? Why there?

So we are talking about infinite loops actually. The faster pointer will enter the loop, and when the diff(longer_pointer, shorter_pointer) == len(loop), they will collide at some point inside the loop. They collide when speed of fastest pointer is len(linked_list).

I guess my HashTable works, but too much space consumption.

## Solution

An easy way to detect if a linked list has a loop is by the slow runner / fast runner approach, FastRunner moves two steps at a time (**not increasing!!**). Eventually, they will meet. When do they collide?

Assume the list has a non-looped part of size `k`. Every `p` steps that SlowRunner takes, FastRunner takes `2p`. When SlowRunner is at position `k`, FastRunner is at `2k`, `k` positions ahead. `k` might be much larger than the loop length, so K = mod(k, loop_size).

1. SlowRunner is 0 steps into the loop
2. FastRunner is `K` steps into the loop
3. SlowRunner is `K` steps behind FastRunner
4. FastRunner is `loop_size - K` steps behind SlowRunner
5. FastRunner catches up to SlowRunner at a rate of 1 step per unit of time.

SlowRunner and FastRunner meet after `loop_size - K` steps, where they will be `K` steps before the head of the loop, at `CollisionSpot`. `CollisionSpot` is K nodesbefore start of loop, and K = mod(k, loop_size), so k = K + M*loop_size for any integer M, so `CollisionSpot` is `k` nodes away from the loop start.

If we keep one pointer at `CollisionSpot` and the other at `head`, and move them at the same speed, they will collide at the beginning of the loop. Then, return node.

[Code in Github (java)](https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2002.%20Linked%20Lists/Q2_08_Loop_Detection/Question.java).