# Detect loop in a linked list

Given a linked list, check if the the linked list has loop or not. Below diagram shows a linked list with a loop.

Following are different ways of doing this
Use Hashing:
Traverse the list one by one and keep putting the node addresses in a Hash Table. At any point, if NULL is reached then return false and if next of current node points to any of the previously stored nodes in Hash then return true.

## C++

 `// C++ program to detect loop in a linked list ` `#include ` `using` `namespace` `std; ` ` `  `/* Link list node */` `struct` `Node ` `{ ` `    ``int` `data; ` `    ``struct` `Node* next; ` `}; ` ` `  `void` `push(``struct` `Node** head_ref, ``int` `new_data) ` `{ ` `    ``/* allocate node */` `    ``struct` `Node* new_node = ``new` `Node; ` ` `  `    ``/* put in the data  */` `    ``new_node->data  = new_data; ` ` `  `    ``/* link the old list off the new node */` `    ``new_node->next = (*head_ref); ` ` `  `    ``/* move the head to point to the new node */` `    ``(*head_ref)    = new_node; ` `} ` ` `  `// Returns true if there is a loop in linked list ` `// else returns false. ` `bool` `detectLoop(``struct` `Node *h) ` `{ ` `    ``unordered_set s; ` `    ``while` `(h != NULL) ` `    ``{ ` `        ``// If this node is already present ` `        ``// in hashmap it means there is a cycle ` `        ``// (Because you we encountering the ` `        ``// node for the second time). ` `        ``if` `(s.find(h) != s.end()) ` `            ``return` `true``; ` ` `  `        ``// If we are seeing the node for ` `        ``// the first time, insert it in hash ` `        ``s.insert(h); ` ` `  `        ``h = h->next; ` `    ``} ` ` `  `    ``return` `false``; ` `} ` ` `  `/* Drier program to test above function*/` `int` `main() ` `{ ` `    ``/* Start with the empty list */` `    ``struct` `Node* head = NULL; ` ` `  `    ``push(&head, 20); ` `    ``push(&head, 4); ` `    ``push(&head, 15); ` `    ``push(&head, 10); ` ` `  `    ``/* Create a loop for testing */` `    ``head->next->next->next->next = head; ` ` `  `    ``if` `(detectLoop(head)) ` `        ``cout << ``"Loop found"``; ` `    ``else` `        ``cout << ``"No Loop"``; ` ` `  `    ``return` `0; ` `} ` `// This code is contributed by Geetanjali `

## Java

 `// Java program to detect loop in a linked list ` `import` `java.util.*; ` ` `  `public` `class` `LinkedList { ` `     `  `    ``static` `Node head;  ``// head of list ` `       `  `    ``/* Linked list Node*/` `    ``static` `class` `Node ` `    ``{ ` `        ``int` `data; ` `        ``Node next; ` `        ``Node(``int` `d) {data = d; next = ``null``; } ` `    ``} ` `   `  `    ``/* Inserts a new Node at front of the list. */` `    ``static` `public` `void` `push(``int` `new_data) ` `    ``{ ` `        ``/* 1 & 2: Allocate the Node & ` `                  ``Put in the data*/` `        ``Node new_node = ``new` `Node(new_data); ` `   `  `        ``/* 3. Make next of new Node as head */` `        ``new_node.next = head; ` `   `  `        ``/* 4. Move the head to point to new Node */` `        ``head = new_node; ` `    ``} ` `  `  `    ``// Returns true if there is a loop in linked ` `    ``// list else returns false. ` `    ``static` `boolean` `detectLoop(Node h) ` `    ``{ ` `        ``HashSet s = ``new` `HashSet(); ` `        ``while` `(h != ``null``) ` `        ``{ ` `             ``// If we have already has this node ` `             ``// in hashmap it means their is a cycle ` `             ``// (Because you we encountering the ` `             ``// node second time). ` `            ``if` `(s.contains(h)) ` `                ``return` `true``; ` `   `  `            ``// If we are seeing the node for ` `            ``// the first time, insert it in hash ` `            ``s.add(h); ` `   `  `            ``h = h.next; ` `        ``} ` `   `  `        ``return` `false``; ` `    ``} ` `     `  `    ``/* Driver program to test above function */` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``LinkedList llist = ``new` `LinkedList(); ` `          `  `        ``llist.push(``20``); ` `        ``llist.push(``4``); ` `        ``llist.push(``15``); ` `        ``llist.push(``10``); ` `          `  `        ``/*Create loop for testing */` `        ``llist.head.next.next.next.next = llist.head; ` `  `  `        ``if` `(detectLoop(head)) ` `            ``System.out.println(``"Loop found"``); ` `        ``else` `            ``System.out.println(``"No Loop"``); ` `     `  `    ``} ` `} ` ` `  `// This code is contributed by Arnav Kr. Mandal. `

## Python3

 `# Python program to detect loop ` `# in the linked list ` `  `  `# Node class  ` `class` `Node: ` `  `  `    ``# Constructor to initialize ` `    ``# the node object ` `    ``def` `__init__(``self``, data): ` `        ``self``.data ``=` `data ` `        ``self``.``next` `=` `None` `  `  `class` `LinkedList: ` `  `  `    ``# Function to initialize head ` `    ``def` `__init__(``self``): ` `        ``self``.head ``=` `None` `  `  `    ``# Function to insert a new ` `    ``# node at the beginning ` `    ``def` `push(``self``, new_data): ` `        ``new_node ``=` `Node(new_data) ` `        ``new_node.``next` `=` `self``.head ` `        ``self``.head ``=` `new_node ` `  `  `    ``# Utility function to prit ` `    ``# the linked LinkedList ` `    ``def` `printList(``self``): ` `        ``temp ``=` `self``.head ` `        ``while``(temp): ` `            ``print` `(temp.data,end``=``" "``) ` `            ``temp ``=` `temp.``next` `  `  `  `  `    ``def` `detectLoop(``self``): ` `         ``s ``=` `set``() ` `         ``temp``=``self``.head ` `         ``while` `(temp): ` `         `  `             ``# If we have already has ` `             ``# this node in hashmap it ` `             ``# means their is a cycle ` `             ``# (Because you we encountering ` `             ``# the node second time). ` `            ``if` `(temp ``in` `s): ` `                ``return` `True` `    `  `            ``# If we are seeing the node for ` `            ``# the first time, insert it in hash ` `            ``s.add(temp) ` `    `  `            ``temp ``=` `temp.``next` `         `  `    `  `         ``return` `False` `  `  `# Driver program for testing ` `llist ``=` `LinkedList() ` `llist.push(``20``) ` `llist.push(``4``) ` `llist.push(``15``) ` `llist.push(``10``) ` `  `  `# Create a loop for testing ` `llist.head.``next``.``next``.``next``.``next` `=` `llist.head; ` ` `  `if``( llist.detectLoop()): ` `    ``print` `(``"Loop found"``) ` `else` `: ` `    ``print` `(``"No Loop "``) ` ` `  `# This code is contributed by Gitanjali. `

Output :

```Loop Found
```

Mark Visited Nodes:
This solution requires modifications to basic linked list data structure.  Have a visited flag with each node.  Traverse the linked list and keep marking visited nodes.  If you see a visited node again then there is a loop. This solution works in O(n) but requires additional information with each node.
A variation of this solution that doesn’t require modification to basic data structure can be implemented using hash.  Just store the addresses of visited nodes in a hash and if you see an address that already exists in hash then there is a loop.

Floyd’s Cycle-Finding Algorithm:
This is the fastest method. Traverse linked list using two pointers.  Move one pointer by one and other pointer by two.  If these pointers meet at same node then there is a loop.  If pointers do not meet then linked list doesn’t have loop.

Implementation of Floyd’s Cycle-Finding Algorithm:

## C/C++

 `// C program to detect loop in a linked list ` `#include ` `#include ` ` `  `/* Link list node */` `struct` `Node ` `{ ` `    ``int` `data; ` `    ``struct` `Node* next; ` `}; ` ` `  `void` `push(``struct` `Node** head_ref, ``int` `new_data) ` `{ ` `    ``/* allocate node */` `    ``struct` `Node* new_node = ` `          ``(``struct` `Node*) ``malloc``(``sizeof``(``struct` `Node)); ` ` `  `    ``/* put in the data  */` `    ``new_node->data  = new_data; ` ` `  `    ``/* link the old list off the new node */` `    ``new_node->next = (*head_ref); ` ` `  `    ``/* move the head to point to the new node */` `    ``(*head_ref)    = new_node; ` `} ` ` `  `int` `detectloop(``struct` `Node *list) ` `{ ` `    ``struct` `Node  *slow_p = list, *fast_p = list; ` `  `  `    ``while` `(slow_p && fast_p && fast_p->next ) ` `    ``{ ` `        ``slow_p = slow_p->next; ` `        ``fast_p  = fast_p->next->next; ` `        ``if` `(slow_p == fast_p) ` `        ``{ ` `           ``printf``(``"Found Loop"``); ` `           ``return` `1; ` `        ``} ` `    ``} ` `    ``return` `0; ` `} ` ` `  `/* Drier program to test above function*/` `int` `main() ` `{ ` `    ``/* Start with the empty list */` `    ``struct` `Node* head = NULL; ` ` `  `    ``push(&head, 20); ` `    ``push(&head, 4); ` `    ``push(&head, 15); ` `    ``push(&head, 10); ` ` `  `    ``/* Create a loop for testing */` `    ``head->next->next->next->next = head; ` `    ``detectloop(head); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to detect loop in a linked list ` `class` `LinkedList ` `{ ` `    ``Node head;  ``// head of list ` `  `  `    ``/* Linked list Node*/` `    ``class` `Node ` `    ``{ ` `        ``int` `data; ` `        ``Node next; ` `        ``Node(``int` `d) {data = d; next = ``null``; } ` `    ``} ` `  `  `    ``/* Inserts a new Node at front of the list. */` `    ``public` `void` `push(``int` `new_data) ` `    ``{ ` `        ``/* 1 & 2: Allocate the Node & ` `                  ``Put in the data*/` `        ``Node new_node = ``new` `Node(new_data); ` `  `  `        ``/* 3. Make next of new Node as head */` `        ``new_node.next = head; ` `  `  `        ``/* 4. Move the head to point to new Node */` `        ``head = new_node; ` `    ``} ` ` `  `    ``int` `detectLoop() ` `    ``{ ` `        ``Node slow_p = head, fast_p = head; ` `        ``while` `(slow_p != ``null` `&& fast_p != ``null` `&& fast_p.next != ``null``) { ` `            ``slow_p = slow_p.next; ` `            ``fast_p = fast_p.next.next; ` `            ``if` `(slow_p == fast_p) { ` `                ``System.out.println(``"Found loop"``); ` `                ``return` `1``; ` `            ``} ` `        ``} ` `        ``return` `0``; ` `    ``} ` ` `  `    ``/* Drier program to test above functions */` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``LinkedList llist = ``new` `LinkedList(); ` ` `  `        ``llist.push(``20``); ` `        ``llist.push(``4``); ` `        ``llist.push(``15``); ` `        ``llist.push(``10``); ` `         `  `        ``/*Create loop for testing */` `        ``llist.head.next.next.next.next = llist.head; ` ` `  `        ``llist.detectLoop(); ` `    ``} ` `}  ` `/* This code is contributed by Rajat Mishra. */`

## Python

 `# Python program to detect loop in the linked list ` ` `  `# Node class  ` `class` `Node: ` ` `  `    ``# Constructor to initialize the node object ` `    ``def` `__init__(``self``, data): ` `        ``self``.data ``=` `data ` `        ``self``.``next` `=` `None` ` `  `class` `LinkedList: ` ` `  `    ``# Function to initialize head ` `    ``def` `__init__(``self``): ` `        ``self``.head ``=` `None` ` `  `    ``# Function to insert a new node at the beginning ` `    ``def` `push(``self``, new_data): ` `        ``new_node ``=` `Node(new_data) ` `        ``new_node.``next` `=` `self``.head ` `        ``self``.head ``=` `new_node ` ` `  `    ``# Utility function to prit the linked LinkedList ` `    ``def` `printList(``self``): ` `        ``temp ``=` `self``.head ` `        ``while``(temp): ` `            ``print` `temp.data, ` `            ``temp ``=` `temp.``next` ` `  ` `  `    ``def` `detectLoop(``self``): ` `        ``slow_p ``=` `self``.head ` `        ``fast_p ``=` `self``.head ` `        ``while``(slow_p ``and` `fast_p ``and` `fast_p.``next``): ` `            ``slow_p ``=` `slow_p.``next` `            ``fast_p ``=` `fast_p.``next``.``next` `            ``if` `slow_p ``=``=` `fast_p: ` `                ``print` `"Found Loop"` `                ``return`  ` `  `# Driver program for testing ` `llist ``=` `LinkedList() ` `llist.push(``20``) ` `llist.push(``4``) ` `llist.push(``15``) ` `llist.push(``10``) ` ` `  `# Create a loop for testing ` `llist.head.``next``.``next``.``next``.``next` `=` `llist.head ` `llist.detectLoop() ` ` `  `# This code is contributed by Nikhil Kumar Singh(nickzuck_007) `

Output:

`Found loop`

Time Complexity: O(n)
Auxiliary Space: O(1)

How does above algorithm work?
Please See : How does Floyd’s slow and fast pointers approach work?