Last Updated: 28 Jan, 2021

Linked List Cycle II

Moderate

Asked in companies

Solve now

Problem statement

You are given a singly linked list that may or may not contain a cycle. You are supposed to return the node where the cycle begins, if a cycle exists, else return 'NULL'.

A cycle occurs when a node's next pointer returns to a previous node in the list.

Example:

In the given linked list, there is a cycle starting at position 0, hence we return 0.

Sample Example 1

Input Format :

The first line contains the elements of the singly linked list separated by a single space and terminated by -1; hence, -1 would never be a list element.

The second line contains the integer position 'pos', which represents the position (0-indexed) in the linked list where the tail connects to. If 'pos' is -1, then there is no cycle in the linked list.

Output Format :

For each test case, print the integer position 'pos' which represents the position of (0-indexed) in the linked list which is the first node of the cycle. Print -1 if there is no cycle in the linked list.

Note:

You are not required to print the expected output; it has already been handled. Just implement the function.

Solve now

Approaches

01 Approach

The basic idea of this approach is to check each node as the starting point for the cycle.

Now consider the following steps:

We are going to have two loops outer-loop and inner-loop.
Maintain a count of the number of nodes visited in outer-loop.
For every node of the outer-loop, start the inner loop from the head.
- If the inner-loop visits the node next to the outer-loop node, then we have found the starting point of the cycle which is the current node of inner-loop, otherwise repeat the process for the next iteration of outer-loop.
If outer-loop reaches the end of list or null, then cycle doesn’t exist in the given linked list.

Solve now

02 Approach

We are going to maintain a lookup table(a HashSet) that basically tells if we have already visited a node or not, during the course of traversal.

Visit every node one by one, until null is not reached
Check if the current node is present in the lookup table if present then there is a loop and the current node is the first node of the loop, otherwise, insert the node reference into the lookup table and repeat the process.
If we reach the end of the list or null, then we can come out of the loop and finally, we can say the loop doesn't exist.

Solve now

03 Approach

The basic idea of this approach is to use the technique based on two-pointers (slow and fast). Slow pointer takes a single jump and corresponding to every jump slow pointers take, fast pointer takes two jumps. If there exists a cycle, both slow and fast pointers will reach the exact same node. If there is no cycle in the given linked list, then the fast pointer will reach the end of the linked list well before the slow pointer reaches the end or null.

To get the starting point of the loop we can start moving both pointers again at the same speed such that one pointer (say slow) begins from the head node of the linked list and other pointers (say fast) begins from the meeting point. This time both the pointers will necessarily meet at the starting point of the loop.

You can refer to this article for more details. https://www.codingninjas.com/blog/2020/09/09/floyds-cycle-detection-algorithm/

Now consider the following steps:

Start traversing the linked list using two pointers (slow and fast). Here, the slow pointer will make a jump of one node and the fast pointer will make jumps of 2 nodes.
If both pointers meet at some node then,
- Point the slow pointer to the head node and again start iterating (this time both pointers will make a jump of 1 node).
- Keep moving the slow and the fast pointers unit both of them meet at a common node. This common node will be the starting node of the cycle.
If slow and fast pointers never meet i.e. the fast pointer reaches the end of the linked list then the loop doesn’t exist in the given linked list, hence we will return -1.

Solve now