Hackerrank: Cracking the Coding Interview – Linked Lists: Detect a Cycle

For this problem we can apply a classic algorithm known as the tortoise and hare algorithm by Robert W. Floyd. We will use two pointers, one going faster than the other. If one of them reaches null then we know there are no cycles. Otherwise, eventually, the two pointers will point to the same node in the LinkedList and we will know that a cycle has been detected.

The wikipedia article I have linked also mentions some other algorithms for cycle detection that can be read for fun.

Problem: https://www.hackerrank.com/challenges/ctci-linked-list-cycle

Solution:

boolean hasCycle(Node head) {
    if (head == null || head.next == null) {
        return false;
    }
    Node tortoise = head;
    Node hare = head;
    while (tortoise != null && hare != null) {
        tortoise = tortoise.next;
        hare = hare.next;
        if (hare != null) {
            hare = hare.next;
            if (tortoise == hare) {
                return true;
            }
        }
    }
    return false;
}

Leave a Reply