Home » Technical Interview Questions » LinkedList Interview Questions » Linked List Cycle

Difficulty Level Medium

## Problem Statement

“Linked List Cycle” problem states that you are given a linked list. Find if it contains any loop or not? ## Example

`1->2->3`
`No Loop`

Explanation: The linked list does not contain any loop because if it did then there would’ve been two no des pointing to the same node. Or there would not have been any node having Null as its next node.

```1->2->3->4
^     |
|_____|```
`Yes there exists a loop`

Explanation: Yes there is a loop because node having value 1 and node with value 4 is pointing to the same node 2.

## Using Hashing Method

### Algorithm

```1. Initialize a hash table of type Node.
2. Start traversing the list. While node of the list is not null check if the current value is already stored in the hash table, if yes return true.
3. Else store it in the hash table and increment the pointer of the hash table.
4. Return false.```

We are here using a hash table or HashSet to find if there exists a loop in the linked list. The same technique is used when we need to find if our array contains duplicates. We use HashSet to store the value which we want should not be repeated. Because a HashSet allows storing only a single instance of any element(i.e. it does not allow to store duplicates). This functionality suits our use case. Thus we use a HashSet to check while traversing the linked list if we find the same node twice. we know that there exists a loop in the linked list. But if we can traverse the linked list without finding the same node twice. we know that none of the elements has been repeated and there is no loop in the linked list.

### Code

#### C++ Program to find Linked list cycle

```#include <bits/stdc++.h>
using namespace std;

struct Node{
int data;
struct Node* next;
};

void push(struct Node** head_ref, int new_data){
struct Node* new_node = new Node;

new_node->data = new_data;

}

bool detectCycle(struct Node* h){
unordered_set<Node*> s;
while (h != NULL) {
if (s.find(h) != s.end())
return true;

s.insert(h);

h = h->next;
}

return false;
}

int main(){

cout << "Loop found";
else
cout << "No Loop";

return 0;
}```
`Loop found`

#### Java Program to find Linked list cycle

```import java.util.*;

class Cycle{

static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}

static public void push(int new_data){
Node new_node = new Node(new_data);

}

static boolean detectCycle(Node h){
HashSet<Node> s = new HashSet<Node>();
while(h != null){
if(s.contains(h))
return true;

h = h.next;
}

return false;
}

public static void main(String[] args){
Cycle list = new Cycle();

list.push(20);
list.push(4);
list.push(15);
list.push(10);

System.out.println("Loop found");
else
System.out.println("No Loop");
}
}```
`Loop found`

### Complexity Analysis

#### Time Complexity

O(N) where n is the number of inserted nodes in the given list. Since we have used HashSet or unordered_set which ensures insertion and searching in O(1) which allowed us to achieve linear time complexity.

#### Space Complexity

O(N) because we used a HashSet wherein the worst case we’ll have to insert N nodes.

## Floyd’s Cycle-Finding Algorithm

### Steps

1. Use two pointers slow and fast.
2. Move slow pointer by 1 node and fast at 2 at each step.
3. If both the pointers meet at any point, then the cycle is present.

### Algorithm

```1. Initialize two pointers fast and slow as head of the list.
2. Traverse while fast or slow is not null. Increment slow by 1 node and fast by 2 nodes.
3. Check at each traversal if slow equals to fast, print "Loop found" and return 1.
4. Else return 0 and print "No loop".```

### Code

#### C++ Program to find Linked list cycle

```#include <bits/stdc++.h>
using namespace std;

class Node{
public:
int data;
Node* next;
};

Node* new_node = new Node();

new_node->data = new_data;

}

int detectCycle(Node* list){
Node *slow = list, *fast = list;

while (slow && fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
cout << "Found Loop";
return 1;
}
}
return 0;
}

int main(){

cout<<"No Loop";

return 0;
}
```
`Loop found`

#### Java Program to find Linked list cycle

```class Cycle{

class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}

public void push(int new_data){
Node new_node = new Node(new_data);

}

int detectCycle(){
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
System.out.println("Found loop");
return 1;
}
}
return 0;
}

public static void main(String args[]){
Cycle list = new Cycle();

list.push(20);
list.push(4);
list.push(15);
list.push(10);

if(list.detectCycle()==0)
System.out.println("No loop");
}
}```
`Loop found`

### Complexity Analysis

#### Time Complexity

O(N) where N is the number of inserted nodes in the given list.

#### Space Complexity

O(1) because we used constant extra space. here we had not stored any extra information regarding each of the nodes. Thus we have constant space complexity.

## Marking visited nodes without modifying the linked list data structure

### Algorithm to detect linked list cycle

```1. Initialize an extra node.
2. Traverse through the list while the head is not null. If head->next is null i.e. there is no cycle, return false.
3. Else if head->next is equal to the extra node, return true.
4. Create a node to store the pointer of the next node.
5. Store extra node in a pointer to the next node.
6. Update the head to the next node.
7. Return false.```

Here we created a temporary node, we point all the nodes to this new node. So, if at a time we come across a node that already points the temporary node. Then we know that there exists a loop else the linked list does not contain a cycle.

### Code

#### C++ Program to find Linked list cycle

```#include <iostream>
using namespace std;

struct Node{
int key;
struct Node* next;
};

Node* newNode(int key){
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}

Node* temp = new Node;

return false;
}

return true;
}

}

return false;
}

int main(){

if(found)
cout << "Loop Found";
else
cout << "No Loop";

return 0;
}```
`Loop found`

#### Java Program to find Linked list cycle

```class Cycle{

static class Node {
int key;
Node next;
};

static Node newNode(int key){
Node temp = new Node();
temp.key = key;
temp.next = null;
return temp;
}

}
System.out.println();
}

Node temp = new Node();

return false;
}

return true;
}

}

return false;
}

public static void main(String args[]){

if (found)
System.out.println("Loop Found");
else
System.out.println("No Loop");
}
}```
`Loop found`

### Complexity Analysis

#### Time Complexity

O(N) where N is the number of inserted nodes in the given list.

#### Space Complexity

O(1) because we used constant extra space. Here we had created just a single new node to which all other nodes point.

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions