Solution: Linked List Cycle

This review provides a detailed analysis of the different ways to solve the Detect a Loop in a Linked List challenge.

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.

  • 00 \leq n 500\leq 500

  • 5×103-5 \times 10^3 \leq Node.data 5×103\leq 5\times 10^3

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 and p2, 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 move p2 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.