Detect Loop or Cycle in Linked List
Last Updated : 18 Jan, 2025
Given a singly linked list, check if the linked list has a loop (cycle) or not. A loop means that the last node of the linked list is connected back to a node in the same list.
Examples:
Input: head: 1 -> 3 -> 4 -> 3
Output: true
Input: head: 1 -> 8 -> 3 -> 4 -> NULL
Output: false
[Naive Approach] Using HashSet - O(n) Time and O(n) Space
The idea is to insert the nodes in the Hashset while traversing and whenever a node is encountered that is already present in the hashset (which indicates there's a cycle (loop) in the list) then return true. If the node is NULL, represents the end of Linked List, return false as there is no loop.
C++ // C++ program to detect loop in a linked list // using hashset #include <iostream> #include <unordered_set> using namespace std; class Node { public: int data; Node* next; Node(int x) { this->data = x; this->next = nullptr; } }; bool detectLoop(Node* head) { unordered_set<Node*>st; while (head != nullptr) { // If this node is already present // in hashmap it means there is a cycle if (st.find(head) != st.end()) return true; // If we are seeing the node for // the first time, insert it in hash st.insert(head); head = head->next; } return false; } int main() { // Create a hard-coded linked list: // 1 -> 3-> 4 Node* head = new Node(1); head->next = new Node(3); head->next->next = new Node(4); // Create a loop head->next->next->next = head->next; if (detectLoop(head)) cout << "true"; else cout << "false"; return 0; } // Java program to detect loop in a linked list // using hashset import java.util.HashSet; class Node { int data; Node next; Node(int x) { this.data = x; this.next = null; } } class GfG { static boolean detectLoop(Node head) { HashSet<Node> st = new HashSet<>(); while (head != null) { // If this node is already present // in hashmap it means there is a cycle if (st.contains(head)) return true; // If we are seeing the node for // the first time, insert it in hash st.add(head); head = head.next; } return false; } public static void main(String[] args) { // Create a hard-coded linked list: // 1 -> 3-> 4 Node head = new Node(1); head.next = new Node(3); head.next.next = new Node(4); // Create a loop head.next.next.next = head.next; if (detectLoop(head)) System.out.println("true"); else System.out.println("false"); } } # Python program to detect loop in a linked list # using hashset class Node: def __init__(self, x): self.data = x self.next = None def detectLoop(head): st = set() while head is not None: # If this node is already present # in hashmap it means there is a cycle if head in st: return True # If we are seeing the node for # the first time, insert it in hash st.add(head) head = head.next return False if __name__ == "__main__": # Create a hard-coded linked list: # 1 -> 3 -> 4 head = Node(1) head.next = Node(3) head.next.next = Node(4) # Create a loop head.next.next.next = head.next if detectLoop(head): print("true") else: print("false") // C# program to detect loop in a linked list // using hashset using System; using System.Collections.Generic; class Node { public int data; public Node next; public Node(int x) { this.data = x; this.next = null; } } class GfG { static bool detectLoop(Node head) { HashSet<Node> st = new HashSet<Node>(); while (head != null) { // If this node is already present // in hashmap it means there is a cycle if (st.Contains(head)) return true; // If we are seeing the node for // the first time, insert it in hash st.Add(head); head = head.next; } return false; } static void Main() { // Create a hard-coded linked list: // 1 -> 3 -> 4 Node head = new Node(1); head.next = new Node(3); head.next.next = new Node(4); // Create a loop head.next.next.next = head.next; if (detectLoop(head)) Console.WriteLine("true"); else Console.WriteLine("false"); } } // JavaScript program to detect loop in a linked list // using hashset class Node { constructor(x) { this.data = x; this.next = null; } } function detectLoop(head) { const st = new Set(); while (head !== null) { // If this node is already present // in hashmap it means there is a cycle if (st.has(head)) return true; // If we are seeing the node for // the first time, insert it in hash st.add(head); head = head.next; } return false; } // Driver Code // Create a hard-coded linked list: // 1 -> 3 -> 4 let head = new Node(1); head.next = new Node(3); head.next.next = new Node(4); // Create a loop head.next.next.next = head.next; if (detectLoop(head)) console.log("true"); else console.log("false"); Time complexity: O(n), where n is the number of nodes in the Linked List.
Auxiliary Space: O(n), n is the space required to store the value in the hash set.
[Expected Approach] Using Floyd's Cycle-Finding Algorithm - O(n) Time and O(1) Space
This idea is to use Floyd's Cycle-Finding Algorithm to find a loop in a linked list. It uses two pointers slow and fast, fast pointer move two steps ahead and slow will move one step ahead at a time.
Follow the steps below to solve the problem:
- Traverse linked list using two pointers.
- Move one pointer(slow) by one step ahead and another pointer(fast) by two steps ahead.
- If these pointers meet at the same node then there is a loop. If pointers do not meet then the linked list doesn't have a loop.
Below is the illustration of above algorithm:
For more details about the working & proof of this algorithm, Please refer to this article, How does Floyd’s Algorithm works.
C++ // C++ program to detect loop in a linked list // using Floyd's Cycle-Finding Algorithm #include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; Node(int x) { this->data = x; this->next = nullptr; } }; bool detectLoop(Node* head) { // Fast and slow pointers initially points to the head Node *slow = head, *fast = head; // Loop that runs while fast and slow pointer are not // nullptr and not equal while (slow && fast && fast->next) { slow = slow->next; fast = fast->next->next; // If fast and slow pointer points to the same node, // then the cycle is detected if (slow == fast) { return true; } } return false; } int main() { // Create a hard-coded linked list: // 1 -> 3-> 4 Node* head = new Node(1); head->next = new Node(3); head->next->next = new Node(4); // Create a loop head->next->next->next = head->next; if (detectLoop(head)) cout << "true"; else cout << "false"; return 0; } // C program to detect loop in a linked list // using Floyd's Cycle-Finding Algorithm #include <stdbool.h> #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; int detectLoop(struct Node* head) { // Fast and slow pointers initially points to the head struct Node *slow = head, *fast = head; // Loop that runs while fast and slow pointer are not // nullptr and not equal while (slow && fast && fast->next) { slow = slow->next; fast = fast->next->next; // If fast and slow pointer points to the same node, // then the cycle is detected if (slow == fast) { return true; } } return false; } struct Node* createNode(int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = NULL; return new_node; } int main() { // Create a hard-coded linked list: // 1 -> 3-> 4 struct Node* head = createNode(1); head->next = createNode(3); head->next->next = createNode(4); // Create a loop head->next->next->next = head->next; if (detectLoop(head)) printf("true"); else printf("false"); return 0; } // Java program to detect loop in a linked list // using Floyd's Cycle-Finding Algorithm class Node { int data; Node next; public Node(int x) { this.data = x; this.next = null; } } class GfG { static boolean detectLoop(Node head) { // Fast and slow pointers initially points to the head Node slow = head, fast = head; // Loop that runs while fast and slow pointer are not // null and not equal while (slow != null && fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; // If fast and slow pointer points to the same node, // then the cycle is detected if (slow == fast) { return true; } } return false; } public static void main(String[] args) { // Create a hard-coded linked list: // 1 -> 3 -> 4 Node head = new Node(1); head.next = new Node(3); head.next.next = new Node(4); // Create a loop head.next.next.next = head.next; if (detectLoop(head)) System.out.println("true"); else System.out.println("false"); } } # Python program to detect loop in a linked list # using Floyd's Cycle-Finding Algorithm class Node: def __init__(self, x): self.data = x self.next = None def detectLoop(head): # Fast and slow pointers initially points to the head slow = head fast = head # Loop that runs while fast and slow pointer are not # None and not equal while slow and fast and fast.next: slow = slow.next fast = fast.next.next # If fast and slow pointer points to the same node, # then the cycle is detected if slow == fast: return True return False if __name__ == "__main__": # Create a hard-coded linked list: # 1 -> 3 -> 4 head = Node(1) head.next = Node(3) head.next.next = Node(4) # Create a loop head.next.next.next = head.next if detectLoop(head): print("true") else: print("false") // C# program to detect loop in a linked list // using Floyd's Cycle-Finding Algorithm using System; class Node { public int data; public Node next; public Node(int x) { this.data = x; this.next = null; } } class GfG { static bool detectLoop(Node head) { // Fast and slow pointers initially points to the head Node slow = head, fast = head; // Loop that runs while fast and slow pointer are not // null and not equal while (slow != null && fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; // If fast and slow pointer points to the same node, // then the cycle is detected if (slow == fast) { return true; } } return false; } static void Main() { // Create a hard-coded linked list: // 1 -> 3 -> 4 Node head = new Node(1); head.next = new Node(3); head.next.next = new Node(4); // Create a loop head.next.next.next = head.next; if (detectLoop(head)) Console.WriteLine("true"); else Console.WriteLine("false"); } } // JavaScript program to detect loop in a linked list // using Floyd's Cycle-Finding Algorithm class Node { constructor(x) { this.data = x; this.next = null; } } function detectLoop(head) { // Fast and slow pointers initially points to the head let slow = head, fast = head; // Loop that runs while fast and slow pointer are not // null and not equal while (slow && fast && fast.next) { slow = slow.next; fast = fast.next.next; // If fast and slow pointer points to the same node, // then the cycle is detected if (slow === fast) { return true; } } return false; } // Driver Code // Create a hard-coded linked list: // 1 -> 3 -> 4 let head = new Node(1); head.next = new Node(3); head.next.next = new Node(4); // Create a loop head.next.next.next = head.next; if (detectLoop(head)) console.log("true"); else console.log("false"); Time complexity: O(n), where n is the number of nodes in the Linked List.
Auxiliary Space: O(1).
Related Articles: