Detect linked list cycle
Difficulty: Medium, Asked-in: Google, Amazon, Microsoft, Goldman Sachs, Nvidia Show
Key takeaway: This is one of the popular linked-list problems to learn problem-solving using the idea of fast and slow pointers. We can solve a lot of other linked list problems using a similar idea. Lets understand theproblemGiventhe head of a linked list, write a program to determine if the linked list has a cycle in it. Return trueif there is a cycle, otherwise, return false. Example 1 Input: Output: true Explanation: Nodes with values 3 and 11 point to the node with value 3 and form a cycle in the input linked list. So we return true. Example 2 Input: 2 -> 20 -> 6 -> 19 -> 13 -> 4 Output: false Explanation: There is no cycle in the linked list. So we return false. A critical note related to the problem In singly linked list problems, we are typically given a link to the first node, and we perform common operations like traversal, searching insertion, deletion, merging, etc. Algorithms for these operations generally require a well-formed linked list i.e. linked list without loops or cycles. If a linked list has a cycle:
A linked list with a cycle causes iteration to fail because the iteration will never reach the end. Therefore, it is desirable to detect that a linked list has no cycle before trying an iteration. So, we are going to discuss various algorithms to detect a loop in a singly linked list. Discussed solution approaches
A brute force approach using a hash tableSolution Idea The basic idea is to traverse the linked list, store the visited nodes, and If the visited node encounters again during the traversal, then it means there is a cycle. Otherwise, if we reach the end of the linked list or discover a NULL pointer, it means there is no cycle. But how do we store the visited nodes and search their duplicate presence? Think! We can use the hash table because it can perform insert and search operations efficiently in O(1) time complexity on average. Solution Steps
Solution Pseudocode Time and space complexity analysis Only one traversal of the linked list is needed in the above code. In other words, the algorithm is performing insert & search operations only once for each node in the linked list. Time complexity = n*O(1) =O(n).We are using a hash table for storing node addresses, so space complexity = O(n) Using boolean flag inside linked list node (augmentation)Solution Idea Here we are optimizing the above approach by avoiding the overhead of hash table operations. The idea would be to modify the linked list node structure and add an extra boolean flag in the definition of the linked list node. This could help us mark the visited nodes and identify their duplicate presence, i.e. whenever the node is visited, it is marked 1, and if we encounter the node with a marked flag again, there is a cycle. Solution Pseudocode Time and space complexity analysis It is working in O(n) time complexity as the algorithm is traversing each node once. We are using an extra variable with each node, so space complexity = O(n) An efficient approach using Floyds cycle detection algorithmSolution Idea The above solutions use O(n) space, so the critical question is: can we optimize further and solve it using O(1) space complexity? The idea of an O(1) space solution is based onFloyds cycle-finding algorithmthat uses only two pointers at different speeds: aslowpointer and afastpointer. At each step of the iteration, the slow pointer moves 1 step simultaneously while the fast pointer moves two steps at a time. It is also called thetortoise and the hare algorithm.
The above idea works because of the following critical facts:
Solution Pseudocode Time and space complexity analysis Suppose for the analysis purpose :
Case 1 : When there is no loop in the linked list then the fast pointer will reach the end after n/2 steps. So time complexity = O(n) Case 1 : When there is a loop in the linked list. The slow or fast pointer will move m steps in the linked list before the slow pointer enters the loop. Now inside the loop, both pointers will travels (l - k) steps before meeting at some common point. (Think!) So total no of steps traveled by both pointers = m + (l - k) = l + m - k = n - k. So what would be the value of k? Let's think! If the slow pointer travels m distance from the start to reach the bridge point, then the fast pointer will travel 2m distance from the start. In this situation, there will be two cases:
So overall, time complexity would be O(n) in the worst-case. The algorithm is working in constant space, space complexity: O(1) Critical ideas to think!
Comparison of time and space complexities
Suggested problems to practiceEnjoy learning, Enjoy problem-solving, Enjoy algorithms! |