How to find the start of a loop in a Linked List?

In the previous post, we saw that we can find out if there is a loop in a Linked list.
Here, we will see how to find the start of a loop.

First, we'll use Floyd’s Cycle-Finding Algorithm again to first find the loop, and then we will add some additional logic to find the start of the loop.

Here is the logic for finding the loop (the same as we did in the previous post):

// Floyd's cycle detection algorithm
public Node<T> findStartOfALoop() {
    Node<T> fast = head;
    Node<T> slow = head;

    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;

        if (fast == slow) { // if yes, we've found the loop
            return findStart(slow);
        }
    }

    return null;
}

Now, we implement the findStart(Node<T> slow) method for finding the start of the loop:

private Node<T> findStart(Node<T> slow) {
    Node<T> temp = head;

    while (temp != slow) {
        temp = temp.next;
        slow = slow.next;
    }

    return temp; // start of the loop
}

Here, we create a temp variable that points to the head, and we leave the slow pointing to the same node where it met the fast pointer before. 

Now, we just start moving them one step at a time, and the node where the pointers meet is actually the start of the loop.

Why this works? This is very good explained in this video: Why Floyd's Detection Cycle algorithm works?

Another way of detecting the start of the loop is using the Set. We start adding the nodes that the current pointer visited and we check if the node is already present in a Set.
If yes, the current node is the start of the loop, since it is the first node that we have already encountered before.

public Node<T> findStartOfALoop() {
    if (head == null) {
        throw new RuntimeException("List is empty");
    }

    Set<Node<T>> set = new HashSet<>();
    Node<T> current = head;

    while (current != null) {
        if (set.contains(current)) {
            return current;
        } else {
            set.add(current);
        }

        current = current.next;
    }

    return null; // if the loop does not exist
}

That is all about how to find the start of a loop in a Linked list.