Solution: Linked List Cycle—Hashing

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.

• $0 \leq$ n $\leq 500$

• $-5 \times 10^3 \leq$ Node.value $\leq 5\times 10^3$

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:

1. Initialize an unordered set visited to store the nodes that have been visited.

2. Initialize a pointer current to the head of the linked list.

3. Traverse the linked list using the current pointer until current becomes NULL (reaches the end of the list). While traversing, perform the following steps:

   1. Check if the current is already in the visited set. If it is, this indicates that there is a cycle in the linked list, so return TRUE.

   2. If the current is not in the visited set, add the current to the set.

   3. Move current to the next node in the linked list (current = current->next) to proceed to the next iteration.

4. 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: