Difficulty: Medium, Asked-in: Google, Amazon, Microsoft, Goldman Sachs, Nvidia
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.
Given the head of a linked list, write a program to determine if the linked list has a cycle in it. Return true if there is a cycle, otherwise, return false.
Example 1
Input linked list with head pointer
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.
Solution 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
bool detectLoop(ListNode head)
{
HashTable <ListNode> H
while (head != NULL)
{
if (H.search(head) == true)
return true
H.insert(head)
head = head->next
}
return false
}
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)
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
class ListNode
{
int data
ListNode next
int flag = 0
}
bool detectLoop(ListNode head)
{
while (head != NULL)
{
if (head->flag == 1)
return true
head->flag == 1
head = head->next
}
return false
}
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)
Solution 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 on Floyd’s cycle-finding algorithm that uses only two pointers at different speeds: a slow pointer and a fast pointer. 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 the “tortoise and the hare algorithm.”
The above idea works because of the following critical facts:
Solution Pseudocode
bool detectLoop(ListNode head)
{
ListNode slow = head
ListNode fast = head
while (slow && fast && fast->next)
{
slow = slow->next
fast = fast->next->next
if (slow == fast)
return true
}
return false
}
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)
Enjoy learning, Enjoy problem-solving, Enjoy algorithms!
Given an array and a positive integer k, write a program to find the kth smallest element in the array. This is an excellent problem to learn problem-solving using the heap data structure. The quick-select approach (divide and conquer) is also worth exploring that helps optimize time complexity to O(n) time average.
You are given a row-wise sorted 2D matrix and a given integer k, write a program to find whether the integer ‘k’ is present in the matrix or not. The matrix has the following properties: Integers in each row are sorted from left to right and the first integer of each row is greater than the last integer of the previous row.
Given a binary tree, write a program to find its height. The height or depth of a binary tree is equal to the count of nodes on the longest path from the root to the leaf, i.e., the max number of nodes from the root to the most distant leaf. This is an excellent problem to learn problem-solving using DFS and BFS traversal.
Bloom filter is a space-efficient data structure that tells whether an element may be in a set (either a false positive or true positive) or definitely not present in a set (True negative). It will take O(1) space, regardless of the number of items inserted. However, their accuracy decreases as more elements are added.
A Segment Tree is a data structure used to answer multiple range queries on an array efficiently. Also, it allows us to modify the array by replacing an element or an entire range of elements in logarithmic time. This blog will focus on the build and query operations on segment trees.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.