Linked Lists: Detect a Cycle HackerRank Solution

Linked Lists: Detect a Cycle HackerRank Solution
Source : https://www.hackerrank.com/challenges/ctci-linked-list-cycle

A linked list is said to contain a cycle if any node is visited more than once while traversing the list. For example, in the following graph there is a cycle formed when node points back to node .

Function Description

Complete the function has_cycle in the editor below. It must return a boolean true if the graph contains a cycle, or false.

has_cycle has the following parameter(s):

• : a pointer to a Node object that points to the head of a linked list.

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

Input Format

There is no input for this challenge. A random linked list is generated at runtime and passed to your function.

Constraints

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 Output

01

Explanation

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

Source : https://www.hackerrank.com/challenges/ctci-linked-list-cycle

Solution

	// Karthikalapati.blogspot.com
	// Algorithm
	//
	// 1. Create a pointer that moves 1 step at a time: 'slow'
	// 2. Create a pointer that moves 2 steps at a time: 'fast'
	// 3. If the Linked List has a cycle, 'slow' and 'fast' will collide.
	/*
	A Node is defined as:
	class Node {
	int data;
	Node next;
	}
	*/
	// If "slow" and "fast" collide, we must have a cycle
	boolean hasCycle(Node head) {
	if (head == null) {
	return false;
	}
	Node slow = head; // moves 1 Node at a time
	Node fast = head; // moves 2 Nodes at a time
	while (fast != null && fast.next != null) {
	slow = slow.next;
	fast = fast.next.next;
	if (slow == fast) {
	return true; // since "slow" and "fast" collided
	}
	}
	return false;
	}
	// Time Complexity: O(n)
	// Space Complexity: O(1)