Cycle Detection Hackerrank problem solution

Cycle Detection Hackerrank

A linked list is said to contain a cycle if any node is visited more than once while traversing the list.

Complete the function provided for you in your editor. It has one parameter: a pointer to a Node object named that points to the head of a linked list. Your function must return a boolean denoting whether or not there is a cycle in the list. If there is a cycle, return true; otherwise, return false.

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

Input Format

Our hidden code checker passes the appropriate argument to your function. You are not responsible for reading any input from stdin.

Constraints

0<=list size<=100 Output Format

If the list contains a cycle, your function must return true. If the list does not contain a cycle, it must return false. The binary integer corresponding to the boolean value returned by your function is printed to stdout by our hidden code checker.

Sample Input

The following linked lists are passed as arguments to your function:

Sample Inputs

Cycle Detection Hackerrank
Sample Output

0
1
Explanation

The first list has no cycle, so we return false and the hidden code checker prints 0 to stdout.
The second list has a cycle, so we return true and the hidden code checker prints 1 to stdout.

Solution

There are 3 scenarios to consider:
The list is empty (i.e., head is null).
The list does not contain a cycle, so you can traverse the list and terminate once there are no more nodes (i.e., next is null).
The list contains a cycle, so you will be stuck looping forever if you attempt to traverse it.

To solve this problem, we must traverse the list using two pointers that we’ll refer to as slow and fast. Our slow pointer moves forward 1 node at a time, and our fast pointer moves forward 2 nodes at a time. If at any point in time these pointers refer to the same object, then there is a loop; otherwise, the list does not contain a loop.

We recommend that you check out Floyd’s Tortoise and Hare cycle-finding algorithm.

bool has_cycle(Node* head) {
    Node* fast = head;
    Node* slow = head;
    while(fast != NULL && slow != NULL && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow) {
            return 1;
        }
    }
    
    return 0;
}
boolean hasCycle(Node head) {
    Node fast = head;
    
    while(fast != null && fast.next != null) {
        fast = fast.next.next;
        head = head.next;
        
        if(head.equals(fast)) {
            return true;
        }
    }
    return false;
}
/*
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) { 
    if(head.data == -1) { return true; } 
    else { int a = head.data; 
          head.data = -1; 
          boolean x = hasCycle(head.next);
          head.data = a; return x; 
         }
} 
    return false; }
def has_cycle(head):
    fast = head;
    
    while(fast != None and fast.next != None):
        fast = fast.next.next;
        head = head.next;
        
        if(head == fast):
            return True;
        
    return False;

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

2 comments: On Cycle Detection Hackerrank problem solution

  • Hi , I do believe this is a great site. I stumbled upon it
    on Yahoo , I shall come back once again.

  • I wanted to thank you for this great read!! I definitely enjoying every
    small touch of it I have you bookmarked to take a look at new material
    you post.

Leave a reply:

Your email address will not be published.