Problem Statement:
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Input 1:
Output 1:
true
Example 2:
Input 2:
Output 2:
false
Approach 1 (Brute-force approach):
First, let’s try to understand what is the difference between this linked list and a regular linked list that we have. Consider the linked list given in input example 1, The difference between this list and the regular list is that, in this list, there are two nodes whose next pointers are the same whereas in regular singly-linked lists (without a loop) each node’s next pointer is unique (when we say unique, we are considering addresses and not data values).
That means the repetition of the next pointers indicates the existence of a loop.
For example, in the first case, the 3rd node (with data value 1) and the last node (with data value 8) both point to node 5 which means there is a loop, as two different nodes point to the same node.
One simple and brute force way of solving this problem is, to start with the first node and see whether there is any node whose next pointer is the current node’s address. If there is a node with the same
address then that indicates that some other node is pointing to the current node and we can say a
loop exists. Continue this process for all the nodes of the linked list.
Does this approach work?
No! Because, we can’t find the end of the linked list. And because we can’t find the end of the linked list, we cannot change our iteration. And hence we will keep revolving within the loop.
Can we use hashing?
Yes! Let’s look at the intuition of why hashing can work here.
- Traverse the linked list nodes one by one.
- Check if the address of the node is available in the hash_map or not.
- If it is already available in the hash_map, that indicates that we are visiting the node
that was already visited. This is possible only if the given linked list has a loop in
it. - If the address of the node is not available in the hash_map, insert that node’s address
into the hash_map. - Continue this process until we reach the end of the linked list or we find the loop.
So, following the above scenarios, we will reach the node with address A12 and we will store it as well (as shown below).
hash_map : {
A1 : true,
A2 : true,
A3 : true,
A4 : true,
A5 : true,
.
.
.
A12 : true
}
Now, we will move to the next node which is A4 and now we will check whether we have A4 in hash_map or not. Since we already have this node in the hash_map we will return true.
Time Complexity:
O(N) for scanning the whole linked list.
Space Complexity:
O(N) for using HashMap
Approach 2 (Optimized):
This problem is solved using Floyd Cycle Detection Algorithm. The very basic idea of this algorithm is that it uses two pointers moving at different speeds to traverse the linked list. Once they enter the loop they are expected to meet, which denotes that there is a loop.
Think of a tortoise and a hare running on a circular track. The faster running hare will catch up with the tortoise if they are running in a loop.
Let’s visualize this by an example:
As you can see, Initially we have slow and fast pointing to the head node. Therefore, we are moving our slow pointer by one time and fast pointer by two times.
Now, if there is a loop, these two pointers will definitely meet. Otherwise, fast will reach the end of the linked list. And as soon as they will meet. We will return true else false.
Let’s look at the code:
Java Code:
/* Below is the structute of a node which is used to create a new node every time. */
class Node {
int data;
Node next;
public Node(int key) {
data = key;
next = null;
}
}
/* Creating a class for implementing the code for Detecting a Loop in a Linked List. */
class LoopDetection {
static Node head;
LoopDetection() {
head = null;
}
/* Utility code for inserting into the linked list. */
void push(int key) {
Node h = head;
if(h == null) {
Node temp = new Node(key);
temp.next = null;
head = temp;
}
else {
while(h.next != null) {
h = h.next;
}
Node temp = new Node(key);
temp.next = null;
h.next = temp;
}
}
/* finding loop in the list */
boolean isLoopFound() {
Node fast, slow;
fast = slow = head;
if(head == null) {
return false;
}
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if(slow == fast) {
return true;
}
}
return false;
}
/* Main method. */
public static void main(String args[]) {
LoopDetection list = new LoopDetection();
list.push(3);
list.push(4);
list.push(5);
list.push(6);
list.push(7);
list.head.next.next.next.next.next = list.head.next.next;
boolean loopFound = list.isLoopFound();
System.out.println(loopFound);
System.out.println();
}
}
Output:
true
CPP Code:
#include <iostream>
using namespace std;
/* creating a node structure in C/C++ */
struct Node {
int data;
struct Node *next;
};
/* defining head as null as there is no node in the list initially. */
struct Node* head = NULL;
void push(int data) {
Node *temp;
temp = head;
/* creating a node and assigning data to it and make its next as null */
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = NULL;
/* check if it's empty make new_node as head */
if(head == NULL) {
head = new_node;
}
/* otherwise move upto the last and then connect last node with the new_node */
else {
while(temp->next != NULL) {
temp = temp->next;
}
temp->next = new_node;
}
}
/* finding loop in a linked list */
bool isLoopFound() {
Node *slow, *fast;
slow = fast = head;
if(head == NULL) {
return false;
}
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if(slow == fast) {
return true;
}
}
return false;
}
int main() {
push(2);
push(3);
push(4);
push(5);
push(6);
head->next->next->next->next->next = head->next->next;
bool loopFound = isLoopFound();
cout << loopFound << endl;
return 0;
}
Output:
true
Python Code:
# Below is the structute of a node which is used to create a new node every time.
class Node:
def __init__(self, data):
self.data = data
self.next = None # None is nothing but null
# Creating a class for implementing the code for Loop Detection in a LinkedList
class LinkedList:
# Whenever we'll create the object of a LinkedList class head will be pointing to null initially
def __init__(self):
self.head = None
# Inserting at the end of a Linked List (append function)
def append(self, key):
h = self.head
if h is None:
new_node = Node(key)
self.head = new_node
else:
while h.next != None:
h = h.next
new_node = Node(key)
h.next = new_node
# finding loop in a linked list
def isLoopFound(self):
fast = self.head
slow = self.head
if self.head is None:
return False
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# Code execution starts here
if __name__=='__main__':
myList = LinkedList()
myList.append(3)
myList.append(4)
myList.append(5)
myList.append(6)
myList.append(7)
myList.head.next.next.next.next.next = myList.head.next.next
loopFound = myList.isLoopFound()
print(loopFound)
Output:
true
Time Complexity:
O(N)
Space Complexity:
O(1)