HackerRank LinkedList Cycle Detection Solution

A linked list is said to contain a cycle if any node is visited more than once while traversing the list. Given a pointer to the head of a linked list, determine if it contains a cycle. If it does, return 1. Otherwise, return 0.

Example

head refers to the list of nodes 1 -> 2 -> 3 -> NULL

The numbers shown are the node numbers, not their data values. There is no cycle in this list so return .

head refers to the list of nodes 1 -> 2 -> 3 -> 1 -> NULL

There is a cycle where node 3 points back to node 1, so return 1.

Function Description

Complete the has_cycle function in the editor below.

It has the following parameter:

• SinglyLinkedListNode pointer head: a reference to the head of the list

Returns

• int: 1 if there is a cycle or 0 if there is not

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

Sample Input

References to each of the following linked lists are passed as arguments to your function:

Sample Output

0
1

Explanation

1. The first list has no cycle, so return 0.
2. The second list has a cycle, so return 1.

SOLUTION

This problem is easier to solve than it seems. The fastest way I found to solve is to have two pointers checking against each other, only that one is faster than the other, this way, if there is a cycle, the slowest one will inevitably meet the fastest, which will be trapped in the cycle.

Let’s see how this would run in the second sample input:

First, both pointers will be head, but then one will accelerate by one, pointing to its next.next:

slow = 1 -> slow = 2 -> slow = 3
fast = 1 -> fast = 3 -> fast = 3

I tried to write the solution using JS, but Hackerrank had a bug, so I had to use Python instead:

def has_cycle(head):
    slow = head
    fast = head
    
    while (fast is not None and fast.next is not None):
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return 1
    
    return 0Lenguaje del código: JavaScript (javascript)