In this HackerRank Cycle Detection problem, we have given a pointer to the head of the linked list, we need to determine if the list contains a cycle or not. if true then return 1 otherwise return 0.
Problem solution in Python programming.
#!/bin/python3
import math
import os
import random
import re
import sys
class SinglyLinkedListNode:
def __init__(self, node_data):
self.data = node_data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert_node(self, node_data):
node = SinglyLinkedListNode(node_data)
if not self.head:
self.head = node
else:
self.tail.next = node
self.tail = node
def print_singly_linked_list(node, sep, fptr):
while node:
fptr.write(str(node.data))
node = node.next
if node:
fptr.write(sep)
def has_cycle(head):
visited = set()
f = head
while f:
i = id(f)
if i in visited:
return 1
visited.add(i)
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())
llist = SinglyLinkedList()
for _ in range(llist_count):
llist_item = int(input())
llist.insert_node(llist_item)
extra = SinglyLinkedListNode(-1);
temp = llist.head;
for i in range(llist_count):
if i == index:
extra = temp
if i != llist_count-1:
temp = temp.next
temp.next = extra
result = has_cycle(llist.head)
fptr.write(str(int(result)) + 'n')
fptr.close()
Problem solution in 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 {
static class SinglyLinkedListNode {
public int data;
public SinglyLinkedListNode next;
public SinglyLinkedListNode(int nodeData) {
this.data = nodeData;
this.next = null;
}
}
static class SinglyLinkedList {
public SinglyLinkedListNode head;
public SinglyLinkedListNode tail;
public SinglyLinkedList() {
this.head = null;
this.tail = null;
}
public void insertNode(int nodeData) {
SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);
if (this.head == null) {
this.head = node;
} 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);
}
}
}
static boolean hasCycle(SinglyLinkedListNode head) {
Set<SinglyLinkedListNode> set=new HashSet<>();
while(head!=null){
if(set.contains(head.next))
return true;
set.add(head.next);
head=head.next;
}
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("(rn|[nru2028u2029u0085])?");
for (int testsItr = 0; testsItr < tests; testsItr++) {
int index = scanner.nextInt();
scanner.skip("(rn|[nru2028u2029u0085])?");
SinglyLinkedList llist = new SinglyLinkedList();
int llistCount = scanner.nextInt();
scanner.skip("(rn|[nru2028u2029u0085])?");
for (int i = 0; i < llistCount; i++) {
int llistItem = scanner.nextInt();
scanner.skip("(rn|[nru2028u2029u0085])?");
llist.insertNode(llistItem);
}
SinglyLinkedListNode extra = new SinglyLinkedListNode(-1);
SinglyLinkedListNode temp = llist.head;
for (int i = 0; i < llistCount; i++) {
if (i == index) {
extra = temp;
}
if (i != llistCount-1) {
temp = temp.next;
}
}
temp.next = extra;
boolean result = hasCycle(llist.head);
bufferedWriter.write(String.valueOf(result ? 1 : 0));
bufferedWriter.newLine();
}
bufferedWriter.close();
scanner.close();
}
}
Problem solution in C++ programming.
#include <bits/stdc++.h>
using namespace std;
class SinglyLinkedListNode {
public:
int data;
SinglyLinkedListNode *next;
SinglyLinkedListNode(int node_data) {
this->data = node_data;
this->next = nullptr;
}
};
class SinglyLinkedList {
public:
SinglyLinkedListNode *head;
SinglyLinkedListNode *tail;
SinglyLinkedList() {
this->head = nullptr;
this->tail = nullptr;
}
void insert_node(int node_data) {
SinglyLinkedListNode* node = new SinglyLinkedListNode(node_data);
if (!this->head) {
this->head = node;
} else {
this->tail->next = node;
}
this->tail = node;
}
};
void print_singly_linked_list(SinglyLinkedListNode* node, string sep, ofstream& fout) {
while (node) {
fout << node->data;
node = node->next;
if (node) {
fout << sep;
}
}
}
void free_singly_linked_list(SinglyLinkedListNode* node) {
while (node) {
SinglyLinkedListNode* temp = node;
node = node->next;
free(temp);
}
}
bool has_cycle(SinglyLinkedListNode* head) {
SinglyLinkedListNode* cur1 = head;
SinglyLinkedListNode* cur2 = head;
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');
SinglyLinkedList* llist = new SinglyLinkedList();
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);
}
SinglyLinkedListNode* extra = new SinglyLinkedListNode(-1);
SinglyLinkedListNode* temp = llist->head;
for (int i = 0; i < llist_count; i++) {
if (i == index) {
extra = temp;
}
if (i != llist_count-1) {
temp = temp->next;
}
}
temp->next = extra;
bool result = has_cycle(llist->head);
fout << result << "n";
}
fout.close();
return 0;
}
Problem solution in 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>
char* readline();
typedef struct SinglyLinkedListNode SinglyLinkedListNode;
typedef struct SinglyLinkedList SinglyLinkedList;
struct SinglyLinkedListNode {
int data;
SinglyLinkedListNode* next;
};
struct SinglyLinkedList {
SinglyLinkedListNode* head;
SinglyLinkedListNode* tail;
};
SinglyLinkedListNode* create_singly_linked_list_node(int node_data) {
SinglyLinkedListNode* node = malloc(sizeof(SinglyLinkedListNode));
node->data = node_data;
node->next = NULL;
return node;
}
void insert_node_into_singly_linked_list(SinglyLinkedList** singly_linked_list, int node_data) {
SinglyLinkedListNode* node = create_singly_linked_list_node(node_data);
if (!(*singly_linked_list)->head) {
(*singly_linked_list)->head = node;
} else {
(*singly_linked_list)->tail->next = node;
}
(*singly_linked_list)->tail = node;
}
void print_singly_linked_list(SinglyLinkedListNode* node, char* sep, FILE* fptr) {
while (node) {
fprintf(fptr, "%d", node->data);
node = node->next;
if (node) {
fprintf(fptr, "%s", sep);
}
}
}
void free_singly_linked_list(SinglyLinkedListNode* node) {
while (node) {
SinglyLinkedListNode* temp = node;
node = node->next;
free(temp);
}
}
bool has_cycle(SinglyLinkedListNode* head) {
SinglyLinkedListNode * nodePtr = head;
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;
char* tests_str = readline();
int tests = strtol(tests_str, &tests_endptr, 10);
if (tests_endptr == tests_str || *tests_endptr != ' ') { exit(EXIT_FAILURE); }
for (int tests_itr = 0; tests_itr < tests; tests_itr++) {
char* index_endptr;
char* index_str = readline();
int index = strtol(index_str, &index_endptr, 10);
if (index_endptr == index_str || *index_endptr != ' ') { exit(EXIT_FAILURE); }
SinglyLinkedList* llist = malloc(sizeof(SinglyLinkedList));
llist->head = NULL;
llist->tail = NULL;
char* llist_count_endptr;
char* llist_count_str = readline();
int llist_count = strtol(llist_count_str, &llist_count_endptr, 10);
if (llist_count_endptr == llist_count_str || *llist_count_endptr != ' ') { exit(EXIT_FAILURE); }
for (int i = 0; i < llist_count; i++) {
char* llist_item_endptr;
char* llist_item_str = readline();
int llist_item = strtol(llist_item_str, &llist_item_endptr, 10);
if (llist_item_endptr == llist_item_str || *llist_item_endptr != ' ') { exit(EXIT_FAILURE); }
insert_node_into_singly_linked_list(&llist, llist_item);
}
SinglyLinkedListNode* extra = create_singly_linked_list_node(-1);
SinglyLinkedListNode* temp = llist->head;
for (int i = 0; i < llist_count; i++) {
if (i == index) {
extra = temp;
}
if (i != llist_count-1) {
temp = temp->next;
}
}
temp->next = extra;
bool result = has_cycle(llist->head);
fprintf(fptr, "%dn", result);
}
fclose(fptr);
return 0;
}
char* readline() {
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] = ' ';
}
data = realloc(data, data_length);
return data;
}