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.

Hackerrank Cycle Detection problem solution


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("(\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])?"); SinglyLinkedList llist = new SinglyLinkedList(); 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); } 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 != '\0') { 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 != '\0') { 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 != '\0') { 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 != '\0') { 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, "%d\n", 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] = '\0'; } data = realloc(data, data_length); return data; }