## Algorithm

Problem Name: Data Structures - Cycle Detection

In this HackerRank in Data Structures - Cycle Detection solutions

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 0.

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:

Returns

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

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

Input Format

The code stub reads from stdin and passes the appropriate argument to your function. The custom test cases format will not be described for this question due to its complexity. Expand the section for the main function and review the code if you would like to figure out how to create a custom case.

Constraints

• 0 <= list size <= 1000

Sample Input

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

Sample Output

``````0
1
``````

Explanation

• The first list has no cycle, so return 0.

• The second list has a cycle, so return 1

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int data;
};

};

node->data = node_data;
node->next = NULL;

return node;
}

} else {
}

}

while (node) {
fprintf(fptr, "%d", node->data);

node = node->next;

if (node) {
fprintf(fptr, "%s", sep);
}
}
}

while (node) {
node = node->next;

free(temp);
}
}

// Complete the has_cycle function below.

/*
*
*     int data;
* };
*
*/

int i;

for ( i=0; i  <  1000; i++ )
{
if ( !nodePtr )
break;
nodePtr = nodePtr->next;
}

if ( i >= 1000 )
return true;
else
return false;
}

int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

char* tests_endptr;
int tests = strtol(tests_str, &tests_endptr, 10);

if (tests_endptr == tests_str || *tests_endptr != '\0') { exit(EXIT_FAILURE); }

for (int tests_itr = 0; tests_itr  <  tests; tests_itr++) {
char* index_endptr;
int index = strtol(index_str, &index_endptr, 10);

if (index_endptr == index_str || *index_endptr != '\0') { exit(EXIT_FAILURE); }

llist->tail = NULL;

char* llist_count_endptr;
int llist_count = strtol(llist_count_str, &llist_count_endptr, 10);

if (llist_count_endptr == llist_count_str || *llist_count_endptr != '\0') { exit(EXIT_FAILURE); }

for (int i = 0; i  <  llist_count; i++) {
char* llist_item_endptr;
int llist_item = strtol(llist_item_str, &llist_item_endptr, 10);

if (llist_item_endptr == llist_item_str || *llist_item_endptr != '\0') { exit(EXIT_FAILURE); }

}

for (int i = 0; i  <  llist_count; i++) {
if (i == index) {
extra = temp;
}

if (i != llist_count-1) {
temp = temp->next;
}
}

temp->next = extra;

fprintf(fptr, "%d\n", result);
}

fclose(fptr);

return 0;
}

size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);

while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);

if (!line) { break; }

data_length += strlen(cursor);

if (data_length  <  alloc_length - 1 || data[data_length - 1] == '\n') { break; }

size_t new_length = alloc_length << 1;
data = realloc(data, new_length);

if (!data) { break; }

alloc_length = new_length;
}

if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}

data = realloc(data, data_length);

return data;
}
``````
Copy The Code &

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>

using namespace std;

public:
int data;

this->data = node_data;
this->next = nullptr;
}
};

public:

this->tail = nullptr;
}

void insert_node(int node_data) {

} else {
this->tail->next = node;
}

this->tail = node;
}
};

while (node) {
fout << node->data;

node = node->next;

if (node) {
fout << sep;
}
}
}

while (node) {
node = node->next;

free(temp);
}
}

int result = 0;
while (cur1 && cur2)
{
cur1 = cur1->next;
cur2 = cur2->next;
if (cur2)
{
cur2 = cur2->next;
}

if (cur1 == cur2)
{
result = 1;
break;
}
}
return result;

}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));

int tests;
cin >> tests;
cin.ignore(numeric_limits < streamsize>::max(), '\n');

for (int tests_itr = 0; tests_itr  <  tests; tests_itr++) {
int index;
cin >> index;
cin.ignore(numeric_limits < streamsize>::max(), '\n');

int llist_count;
cin >> llist_count;
cin.ignore(numeric_limits < streamsize>::max(), '\n');

for (int i = 0; i  <  llist_count; i++) {
int llist_item;
cin >> llist_item;
cin.ignore(numeric_limits < streamsize>::max(), '\n');

llist->insert_node(llist_item);
}

for (int i = 0; i  <  llist_count; i++) {
if (i == index) {
extra = temp;
}

if (i != llist_count-1) {
temp = temp->next;
}
}

temp->next = extra;

fout << result << "\n";
}

fout.close();

return 0;
}
``````
Copy The Code &

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

public int data;

this.data = nodeData;
this.next = null;
}
}

this.tail = null;
}

public void insertNode(int nodeData) {

} else {
this.tail.next = node;
}

this.tail = node;
}
}

public static void printSinglyLinkedList(SinglyLinkedListNode node, String sep, BufferedWriter bufferedWriter) throws IOException {
while (node != null) {
bufferedWriter.write(String.valueOf(node.data));

node = node.next;

if (node != null) {
bufferedWriter.write(sep);
}
}
}

return true;
}
return false;
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int tests = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int testsItr = 0; testsItr < tests; testsItr++) {
int index = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

int llistCount = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int i = 0; i  <  llistCount; i++) {
int llistItem = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

llist.insertNode(llistItem);
}

for (int i = 0; i  <  llistCount; i++) {
if (i == index) {
extra = temp;
}

if (i != llistCount-1) {
temp = temp.next;
}
}

temp.next = extra;

bufferedWriter.write(String.valueOf(result ? 1 : 0));
bufferedWriter.newLine();
}

bufferedWriter.close();

scanner.close(>;
}
}
``````
Copy The Code &

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
#!/bin/python3

import math
import os
import random
import re
import sys

def __init__(self, node_data):
self.data = node_data
self.next = None

def __init__(self):
self.tail = None

def insert_node(self, node_data):

else:
self.tail.next = node

self.tail = node

while node:
fptr.write(str(node.data))

node = node.next

if node:
fptr.write(sep)

# Complete the has_cycle function below.

#
#
#     int data
#
#
visited = set()
while f:
i = id(f)
if i in visited:
return 1
f = f.next
return 0

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

tests = int(input())

for tests_itr in range(tests):
index = int(input())

llist_count = int(input())

for _ in range(llist_count):
llist_item = int(input())
llist.insert_node(llist_item)

for i in range(llist_count):
if i == index:
extra = temp

if i != llist_count-1:
temp = temp.next

temp.next = extra