Solution: Linked List Cycle—Hashing
Let’s solve the Linked List Cycle—Hashing problem.
We'll cover the following
Statement
Given the head
of a linked list, check whether or not a cycle is present in the linked list. A cycle is present in a linked list if at least one node can be reached again by traversing the next
pointer. If a cycle exists, return TRUE, otherwise return FALSE.
Constraints:
Let n
be the number of nodes in a linked list.
n
Node.value
Solution
The algorithm uses an unordered set to track visited nodes while traversing the linked list, returning true if a repeated node is encountered (indicating a cycle) and false otherwise.
The steps of the algorithm are given below:
Initialize an unordered set
visited
to store the nodes that have been visited.Initialize a pointer
current
to the head of the linked list.Traverse the linked list using the
current
pointer untilcurrent
becomes NULL (reaches the end of the list). While traversing, perform the following steps:Check if the
current
is already in thevisited
set. If it is, this indicates that there is a cycle in the linked list, so return TRUE.If the
current
is not in thevisited
set, add thecurrent
to the set.Move
current
to the next node in the linked list (current = current->next
) to proceed to the next iteration.
If the traversal completes without finding a repeated node (i.e.,
current
becomes NULL), it means there is no cycle in the linked list and returns FALSE.
Let’s look at the illustration below to better understand the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.