HackerRank LinkedList Cycle Detection Solution

Total
0
Shares

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 0
Lenguaje del código: JavaScript (javascript)
HackerRank LinkedList Cycle Detection Solution
Deja un comentario

Tu dirección de correo electrónico no será publicada.

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

You May Also Like