In the Linked List Cycle problem, we are given a linked list and we have to detect a cycle in this linked list, a linked list cycle occurs when a node in the list points to a previous node, creating a loop within the structure<\/strong>.<\/p>\n\n\n\n Let us understand it better with an example:<\/p>\n\n\n In the above-linked list, there is a cycle where the last node is connected to the previous node.<\/p>\n\n\n\n Learning about linked list cycles is important for building a strong foundation in computer science. It hones problem-solving skills and provides practical knowledge that can be applied in various real-world scenarios.<\/p>\n\n\n\n In this approach we will use a set data structure because a set data structure only stores unique nodes, if there is any cycle then we will get to know through this set data structure.<\/p>\n\n\n\n Here are the steps to solve the problem using this naive approach:<\/p>\n\n\n\n The time complexity of this approach is O(N) as we are iterating through the list only once and N is the size of the linked list. The space complexity of this approach is O(N) as we are using a set and storing N nodes in it.<\/p>\n\n\n\n Using Floyd’s Tortoise & Hare Algorithm, the concept of the slow and fast pointer is used to detect cycles in a linked list.<\/strong> It is based on the learning that whenever we move a pointer with twice the speed of another pointer if there exists any cycle, both will meet somewhere in the cycle. Since the distance will keep on decreasing between the two after every cycle is completed.<\/p>\n\n\n\n Also known as the cycle detection algorithm Floyd’s Tortoise & Hare Algorithm was developed by Robert W. Floyd. The basic idea behind it is to have two pointers, one moving at a slower pace (tortoise) and the other at a faster pace (hare). If there is a cycle in the sequence, the faster pointer will eventually catch up to the slower one, indicating the presence of a cycle.<\/p>\n\n\n\n Below are the steps to be followed to detect a cycle or loop in a linked list using Floyd’s Tortoise and Hare algorithm:<\/p>\n\n\n\n Below is the complete C++ program for Linked List Cycle Detection:<\/p>\n\n\n\n You can detect loop or cycle in linked list using Java as well:<\/p>\n\n\n\n Here is the implementation in Python also:<\/p>\n\n\n\n Output:<\/strong><\/p>\n\n\n\n The time complexity of this approach is O(N) <\/strong>where N is the size of the linked list. In the worst case, all the nodes of the list are visited. The space complexity is O(1) <\/strong>because we are not using any extra space.<\/p>\n\n\n\n Below is a small comparative analysis of both the methods:<\/p>\n\n\n\n You might also want to learn how to detect a cycle in an undirected graph<\/a> as well.<\/p>\n\n\n\n![\"Example](\"https:\/\/lh7-us.googleusercontent.com\/ljiD38qnuA7lcPjNbZELsf1sCwuzkECfginKmYCRiU-tHMICuU7k9zsU-8Th_HmA9RoAWYBYkfr_N_djvzNAUfOLNRyFzDTtWU0ls-szaXsxTl9Qh0086Knpan8aOlOmmq5ZHo_4bLFMIDgLfzkMTxg\")
Using Hashing to Find Linked List Cycle<\/strong><\/h2>\n\n\n\n
\n
![\"1st](\"https:\/\/lh7-us.googleusercontent.com\/gPaWXWUZEos4wOCqp9Otwfs3qM-N_XFAdg7VlTt7MLtgEzd4IM2cu_zdUMSuruc8fDtWaXSct182vG_9gLUV0eDqmLtLp48kQCpZZGoroyGod_uMm4QLr1hNreNFsmdzemW1qFwB0BdHtEhV6D4MEUk\")
\n
\n
![\"2nd](\"https:\/\/lh7-us.googleusercontent.com\/J8TAEfY6eOnqy6dVNjL2_4aDHrpGNsGE0ckBibItfMt-Ps3o3fMdbAfmc2e-sAXIwkGwZA6ABS71hG1MF6s5amGnKwhwChhvBmSVO63tinguBzm-SALgl4bXnT2OGcVYF_SyR9jIxJtEi4bWRUVtvTA\")
\n
![\"3rd](\"https:\/\/lh7-us.googleusercontent.com\/IwPod_VPN6KA9li3iguVpvZUMK3fjGATcDFFGuSr3YRcsMrXW8j3UCChitMDuXmEoobG_dyDyaAsQkdom_TxX8OCL-YScKAhdTquF6B53wT6h5AcZ2GiNsqpiaHX7f2heubRUGnbltZXJohHsCljesQ\")
\n
![\"4th](\"https:\/\/lh7-us.googleusercontent.com\/X2Dp2AFfE2M55EdzhsiJCUeWuuJa3x1ckMkRHUXV5sPU3HtoXp7saA-Mv56GQheMq_2L5vpJ5ic1QcDzMOztEbRe40_YiOJFJF4ol9zdDyvgcRw2HNQHoC_GdNOxJImiU-ggFXtwDzFmCGUiAlSVu6s\")
\n
![\"5th](\"https:\/\/lh7-us.googleusercontent.com\/ElBcdhyMpgULV-54uHsGJIWijR27mMXMw_3YQCSAYrzPBe7x-LX4Pnd_b1fJSIaNCE3y4XvhY1KPac1JiP_7_YCgLJ8RmuHGSnS3sbf66tBLq4mFhV6erDLq7cwMihe8wfCFWNhJBV7LLjaujx5UgtU\")
\n
![\"Node](\"https:\/\/lh7-us.googleusercontent.com\/myNMApIqMhvLXteaCeycs5RR4Emmhw2p1CVXPhUnnXyUtEEqTJndDtWnlry9uOP4-DhzMGY59mUj4m1IKfiwRJfURupE1RjPdh6ExAK-3dSIVCr_KVSxMoIlWhNwUhQl8iRRfB1gGKnGCx9DBXUogxU\")
\n
Floyd’s Tortoise & Hare Algorithm to Detect Linked List Cycle<\/strong><\/h2>\n\n\n\n
\n
![\"Initialise](\"https:\/\/lh7-us.googleusercontent.com\/guyC4U_ja4Aye4ZsIQyq_43bMQyR8hskSExnr5ZWakGo7r_vFN9LBT6tZ6ZdOm8eGximUyQvqjMg_QcW0SwMfiURdrdPrK6L5IwERM5tXM8ae9CzppZtCqEMY9tPOPgIsruaKFJIT63B_8lDBgkFeeM\")
\n
![\"Move](\"https:\/\/lh7-us.googleusercontent.com\/S1tP2bX0LicWKAX79ac-o8NwgszREvXP6dQEEkd9kCS47CpdxPpFirTIZ2UQ09kFjuJKRwVhLKruzrLR8kKM_nbww_4EHbThsZtcdzy9rkUbWuWSukfdbmjdidoVjNJxpu1IXUKEROAj45jEAFW1LBM\")
\n
![\"Move](\"https:\/\/lh7-us.googleusercontent.com\/vCxE_dAYXVdendtdWxaOngwvgbYh4xV71-oZX6kgPtQjdhrhyFEXRFYMFO3lRuQO4ptM03PKxYLj7fEO4huS8Y3xWOkg2R9-BDnKzMj9cBXnIav_MIwvupc_RCJHQFq9w6RxtkkeFGJ8sqF_tNhThbg\")
\n
![\"Both](\"https:\/\/lh7-us.googleusercontent.com\/lQpMPks3cPz7CfnVXr_qnW74Hxb0f-TMTa5M6hmzeBALl5zrCIrBMqbg52Ll_QzJyrxTq1Fqy97wwfUI7HyROJLf4WCk4k47ZV9U_sLNRJMcvf1aOzm2m_GTeapWjkV65pYN4mlAUnT7pahCDyzle2Q\")
C++ Code<\/strong><\/h3>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n\n\/\/ Definition for singly-linked list.\nstruct ListNode {\n int val;\n ListNode* next;\n ListNode(int x) : val(x), next(nullptr) {}\n};\n\nbool hasCycle(ListNode* head) {\n \/\/ Initialize fast and slow pointers\n ListNode* slow = head;\n ListNode* fast = head;\n\n \/\/ Traverse the linked list\n while (fast != nullptr && fast->next != nullptr) {\n \/\/ Move slow pointer one step\n slow = slow->next;\n\n \/\/ Move fast pointer two steps\n fast = fast->next->next;\n\n \/\/ Check if pointers meet, indicating a cycle\n if (slow == fast) {\n return true;\n }\n }\n\n \/\/ If the end of the list is reached and no cycle is detected\n return false;\n}\n\nint main() {\n \/\/ Create a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (cycle)\n ListNode* head = new ListNode(1);\n head->next = new ListNode(2);\n head->next->next = new ListNode(3);\n head->next->next->next = new ListNode(4);\n head->next->next->next->next = new ListNode(5);\n head->next->next->next->next->next = head->next->next; \/\/ Creating a cycle\n\n \/\/ Check if the linked list has a cycle\n if (hasCycle(head)) {\n cout << "The linked list has a cycle." << endl;\n } else {\n cout << "The linked list does not have a cycle." << endl;\n }\n\n return 0;\n}<\/pre><\/div>\n\n\n\nJava Code<\/strong><\/h3>\n\n\n\n
public class LinkedListCycle {\n\n \/\/ Definition for singly-linked list.\n static class ListNode {\n int val;\n ListNode next;\n ListNode(int x) {\n val = x;\n next = null;\n }\n }\n\n public static boolean hasCycle(ListNode head) {\n \/\/ Initialize fast and slow pointers\n ListNode slow = head;\n ListNode fast = head;\n\n \/\/ Traverse the linked list\n while (fast != null && fast.next != null) {\n \/\/ Move slow pointer one step\n slow = slow.next;\n\n \/\/ Move fast pointer two steps\n fast = fast.next.next;\n\n \/\/ Check if pointers meet, indicating a cycle\n if (slow == fast) {\n return true;\n }\n }\n\n \/\/ If the end of the list is reached and no cycle is detected\n return false;\n }\n\n public static void main(String[] args) {\n \/\/ Create a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (cycle)\n ListNode head = new ListNode(1);\n head.next = new ListNode(2);\n head.next.next = new ListNode(3);\n head.next.next.next = new ListNode(4);\n head.next.next.next.next = new ListNode(5);\n head.next.next.next.next.next = head.next.next; \/\/ Creating a cycle\n\n \/\/ Check if the linked list has a cycle\n if (hasCycle(head)) {\n System.out.println("The linked list has a cycle.");\n } else {\n System.out.println("The linked list does not have a cycle.");\n }\n }\n}<\/pre><\/div>\n\n\n\nPython Code<\/strong><\/h3>\n\n\n\n
class ListNode:\n def __init__(self, x):\n self.val = x\n self.next = None\n\ndef hasCycle(head):\n # Initialize fast and slow pointers\n slow = head\n fast = head\n\n # Traverse the linked list\n while fast is not None and fast.next is not None:\n # Move slow pointer one step\n slow = slow.next\n\n # Move fast pointer two steps\n fast = fast.next.next\n\n # Check if pointers meet, indicating a cycle\n if slow == fast:\n return True\n\n # If the end of the list is reached and no cycle is detected\n return False\n\n# Create a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (cycle)\nhead = ListNode(1)\nhead.next = ListNode(2)\nhead.next.next = ListNode(3)\nhead.next.next.next = ListNode(4)\nhead.next.next.next.next = ListNode(5)\nhead.next.next.next.next.next = head.next.next # Creating a cycle\n\n# Check if the linked list has a cycle\nif hasCycle(head):\n print("The linked list has a cycle.")\nelse:\n print("The linked list does not have a cycle.")<\/pre><\/div>\n\n\n\nThe linked list has a cycle.<\/code><\/pre>\n\n\n\nApproaches<\/strong><\/td> Time complexity<\/strong><\/td> Space complexity<\/strong><\/td> Details<\/strong><\/td><\/tr> Hashing Approach<\/td> O(N)<\/td> O(N)<\/td> Here space complexity is O(N) because we are using a set data structure to detect cycle<\/td><\/tr> Optimized approach<\/td> O(N)<\/td> O(1)<\/td> Here no extra space is required in this approach<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n Conclusion<\/strong><\/h2>\n\n\n\n