Header Ad

HackerRank Linked Lists: Detect a Cycle problem solution

In this HackerRank Linked Lists: Detect a Cycle Interview preparation kit problem You need to Complete the function has_cycle that must return a boolean true if the graph contains a cycle, or false.


HackerRank Linked Lists: Detect a Cycle interview preparation kit solution


Problem solution in Python programming.

"""
Detect a cycle in a linked list. Note that the head pointer may be 'None' if the list is empty.

A Node is defined as: 
 
    class Node(object):
        def __init__(self, data = None, next_node = None):
            self.data = data
            self.next = next_node
"""


def has_cycle(head):
    if head is None or head.next is None:
        return False
    head.visited = True
    current = head
    while current.next is not None:
        current = current.next
        if current.visited:
            return True
    return False




Problem solution in Java7 Programming.

/*
Detect a cycle in a linked list. Note that the head pointer may be 'null' if the list is empty.

A Node is defined as: 
    class Node {
        int data;
        Node next;
    }
*/

boolean hasCycle(Node head) {
    if (head == null) return false;
    
    Node slow = head;
    Node fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) return false;
        
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return true;
}


Problem solution in C++ programming.

/*
Detect a cycle in a linked list. Note that the head pointer may be 'NULL' if the list is empty.

A Node is defined as: 
    struct Node {
        int data;
        struct Node* next;
    }
*/

bool has_cycle(Node* head) {
    // Complete this function
    // Do not write the main method
    if ( NULL == head )
        return false;
    
    Node *temp = head;
    Node **visit = new Node *[200];
    int num=0;
    while (temp )
    {
        for (int i=0; i<num; i++)
        {
            if ( visit[i] == temp )
            {
                delete [] visit;
                return true;
            }
        }
        visit[num++] =temp;
        
            temp = temp->next;
    }
    return false;
}


Post a Comment

1 Comments

  1. In the given problem where is mentioned that we can use node.visited in python code given?

    ReplyDelete