This tutorial will provide a step-by-step walkthrough in Python for solving the Linked Lists: Detect a Cycle problem for the section Cracking the Code Interview from Hackerrank. Linked Lists are defined on Wikipedia as:

Linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next.

This means that it's not possible to access each item through an index, such as in an Array. The benefit is Linked Lists are very efficient when removing items or adding items.

Singly-linked-list by Lasindi / CC BY

Description

A linked list is said to contain a cycle if any node is visited more than once while traversing the list.

Complete the function provided in the editor below. It has one parameter: a pointer to a Node object named that points to the head of a linked list. Your function must return a boolean denoting whether or not there is a cycle in the list. If there is a cycle, return true; otherwise, return false.

Note: If the list is empty, head will be null.

Input Format

Our hidden code checker passes the appropriate argument to your function. You are not responsible for reading any input from stdin.

Constraints

• 1 ≤ list size ≤ 100

Output Format

If the list contains a cycle, your function must return true. If the list does not contain a cycle, it must return false. The binary integer corresponding to the boolean value returned by your function is printed to stdout by our hidden code checker.

Sample Input

The following linked lists are passed as arguments to your function

Sample Output

0
1

Explanation

The first list has no cycle, so we return false and the hidden code checker prints 0 to stdout. The second list has a cycle, so we return true and the hidden code checker prints 1 to stdout.

Solution

We will be using Floyd's cycle finding algorithm. This is also known as the tortoise and hare algorithm from the famous fable. There will be two pointers and just like in the children's story, one will move fast while the other goes slow (and steady?). We conclude there is a cycle when the tortoise is at the same location as the hare because he caught up. In this case, the tortoise doesn't catch up because the hare gets tired, they are just pointers after all. They meet when they start going in circles and eventually the hare laps the still slow tortoise.

The Tortoise and the Hare by http://www.gutenberg.org/etext/19993 / CC BY

Let's step through the code. The function for detecting a cycle will accept a node, head, as a parameter. Immediately we see that if head doesn't exist then there is no initial node and the list doesn't even exist. Return false because a non-existent list doesn't have a cycle. Then we set the tortoise (slow) and fast (hare) both at the starting line which is the initial node. They are ready to start the race.

def has_cycle(head):    
    # list doesn't exist so return false immediately
    if head is None:
        return False

    slow = head
    fast = head

Let's start the race while a while loop. The condition doesn't matter because at some point we exit out by returning either false or true. First check that next node exists. If it doesn't then we know that he is at the finish line and can return false. A linked list with a cycle will never have a finish line because it keeps looping and therefore this is case has no cycle. Move the tortoise one "step"/node at a time.

    ...
    while True:

        # first check that that next exists and then do one hop
        if slow.next is None:
            return False
        else:
            slow = slow.next

Now we do the exact same thing for the hare, except the hare moves two "steps"/nodes at a time. 

    ...
        # first check that that two ahead exists and then do two hops
        if fast.next.next is None:
            return False
        else:
            fast = fast.next.next
    ...

If the tortoise ever meets the hare at any point (while being lapped), then there is definitely a cycle. That's the only way he can catch up and we detected the cycle.

    ...
        # when the two meet there must be a loop
        if slow is fast:
            return True

The entire solution is shown below.

Búho nival by Diego Delso / CC BY

"""
Detect a cycle in a linked list. Note that the head pointer may be 'None' if the list is empty.
A Node is defined as:
    class Node(object):
        def __init__(self, data = None, next_node = None):
            self.data = data
            self.next = next_node
"""


def has_cycle(head):
    # use Floyd's cycle Finding Algorithm

    # list doesn't exist so return false immediately
    if head is None:
        return False

    slow = head
    fast = head

    while True:

        # first check that that next exists and then do one hop
        if slow.next is None:
            return False
        else:
            slow = slow.next

        # first check that that two ahead exists and then do two hops
        if fast.next.next is None:
            return False
        else:
            fast = fast.next.next

        # when the two meet there must be a loop
        if slow is fast:
            return True

Tags: Algorithm, Hackerrank, Python