# Linked Lists: Detect a Cycle

### Problem Statement :

```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 5  points back to node 3.

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):

Returns

boolean: True if there is a cycle, False if there is not
Note: If the list is empty, head  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

0   <=  list size  <=  100```

### Solution :

```                        ```Solution in C++ :

In  C++  :

/*

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

#include <unordered_set>

std::unordered_set<Node*> visited;

{
// Empty lists don't have circles.
visited.clear();

return false;
}

// If already in the list of visited nodes.
visited.clear();

// It means we have a cycle.
return true;
}

// Otherwise, remember it.

// Recurse for the rest of the list.
}```
```

```                        ```Solution in Java :

In   Java :

/*

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

return false;
else{
while(fast!=null && fast.next!=null && fast!=slow){
slow=slow.next;
fast=fast.next.next;
}
if( fast!=null && fast==slow)
return true;
return false;
}

}```
```

```                        ```Solution in Python :

In   Python3  :

"""

A Node is defined as:

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

visited = set()
while it.next:
it = it.next
if it in visited:
return True
return False```
```

## Jenny's Subtrees

Jenny loves experimenting with trees. Her favorite tree has n nodes connected by n - 1 edges, and each edge is ` unit in length. She wants to cut a subtree (i.e., a connected part of the original tree) of radius r from this tree by performing the following two steps: 1. Choose a node, x , from the tree. 2. Cut a subtree consisting of all nodes which are not further than r units from node x .

## Tree Coordinates

We consider metric space to be a pair, , where is a set and such that the following conditions hold: where is the distance between points and . Let's define the product of two metric spaces, , to be such that: , where , . So, it follows logically that is also a metric space. We then define squared metric space, , to be the product of a metric space multiplied with itself: . For

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty