Last Updated: 10 Dec, 2019
Cycle Detection in a Singly Linked List
Moderate
Asked in companies
You are given a Singly Linked List of integers. Return true if it has a cycle, else return false.
A cycle occurs when a node's next points back to a previous node in the list.
Example:
In the given linked list, there is a cycle, hence we return true.
Input format :
The first line of each test case 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', representing the position (0-indexed) in the linked list where the tail connects. If 'pos' is -1, there is no cycle in the linked list.
Output format :
The only output line contains 'true' if the linked list has a cycle or 'false' otherwise.
Note :
You don't have to print by yourself explicitly. It has been taken care of.
Approaches
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 head.
- If the inner-loop visits the node next to the outer-loop node, then return true, else repeat the process for the next iteration of outer-loop.
- If outer-loop reaches the end of list or null, then return false.
We are going to maintain a lookup table(a Hashmap) 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 loop up table, if present then there is a cycle and will return true, otherwise, put the node reference into the lookup table and repeat the process.
- If we reach at the end of the list or null, then we can come out of the process or loop and finally, we can say the loop doesn't exist.
- The idea is to have 2 pointers: slow and fast. Slow pointer takes a single jump and corresponding to every jump slow pointer takes, fast pointer takes 2 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 fast pointer will reach the end of the linked list well before the slow pointer reaches the end or null.
- Initialize slow and fast at the beginning.
- Start moving slow to every next node and moving fast 2 jumps, while making sure that fast and its next is not null.
- If after adjusting slow and fast, if they are referring to the same node, there is a cycle otherwise repeat the process
- If fast reaches the end or null then the execution stops and we can conclude that no cycle exists.