Solution: Linked List Cycle
Let's solve the Linked List Cycle 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.data
Solution
We will use Floyd’s cycle-finding algorithm to detect a cycle in the linked list. In this algorithm, we use two pointers to check if a cycle exists in a linked list: a slow pointer that moves one node at a time and a fast pointer that moves two nodes at a time. If there is no cycle in the linked list, the fast pointer will reach the end of the linked list before the slow pointer. If there is a cycle, the fast pointer will eventually catch up to the slow pointer because it moves faster. The following are the steps of the algorithm:
Initialize two pointers,
p1
andp2
, to point to the head of the linked list.Traverse the linked list until the end of the linked list is reached.
While traversing the linked list, move
p1
one node at a time and movep2
two nodes at a time.If at any point the two pointers meet, it means that a cycle has been found. In this case, we return TRUE.
If the end of the linked list is reached, that is,
p2
is pointing to NULL, a cycle does not exist. In this case, we return FALSE.
The following illustration demonstrates the algorithm:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.