Cycle Detection in a Singly Linked List
You have given a Singly Linked List of integers, determine if it forms a cycle or not.

A cycle occurs when a node's next points back to a previous node in the list. The linked list is no longer linear with a beginning and end—instead, it cycles through a loop of nodes.

Note: Since, it is binary problem, there is no partial marking. Marks will only be awarded if you get all the test cases correct.

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 and 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 tail connects to. If "pos" is -1, then there is no cycle in the linked list.

Output format :

The only line of output contains 'true' if linked list has a cycle or 'false' otherwise. You don't have to explicitly print by yourself. It has been taken care of.

Constraints :

0

Question

Cycle Detection in a Singly Linked List

You have given a Singly Linked List of integers, determine if it forms a cycle or not.

A cycle occurs when a node's next points back to a previous node in the list. The linked list is no longer linear with a beginning and end—instead, it cycles through a loop of nodes.

Note: Since, it is binary problem, there is no partial marking. Marks will only be awarded if you get all the test cases correct.

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 and 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 tail connects to. If "pos" is -1, then there is no cycle in the linked list.

Output format :

The only line of output contains 'true' if linked list has a cycle or 'false' otherwise.

You don't have to explicitly print by yourself. It has been taken care of.

Constraints :

0 <= N <= 10^6
-1 <= pos < N
-10^9 <= data <= 10^9 and data != -1

Where 'N' is the size of the singly linked list, "pos" represents the position (0-indexed) in the linked list where tail connects to and "data" is the Integer data of singly linked list.

Time Limit: 1 sec

Note :

Try to solve this problem in O(N) Time Complexity and O(1) space Complexity

Accepted Answer

Floyd's algorithm can be used to solve this question.
Define two pointers slow and fast. Both point to the head node, fast is twice as fast as slow. There will be no cycle if it reaches the end. Otherwise, it will eventually catch up to the slow pointer somewhere in the cycle.
Let X be the distance from the first node to the node where the cycle begins, and let X+Y be the distance the slow pointer travels. To catch up, the fast pointer must travel 2X + 2Y. L is the cycle size. The total distance that the fast pointer has travelled over the slow pointer at the meeting point is what we call the full cycle.
X+Y+L = 2X+2Y
L=X+Y
Based on our calculation, slow pointer had already traveled one full cycle when it met fast pointer, and since it had originally travelled A before the cycle began, it had to travel A to reach the cycle's beginning!
After the two pointers meet, fast pointer can be made to point to head. And both slow and fast pointers are moved till they meet at a node. The node at which both the pointers meet is the beginning of the loop.

Pseudocode :
detectCycle(Node *head) {
Node *slow=head,*fast=head;
while(slow!=NULL && fast!=NULL && fast->next!=NULL) {
slow = slow->next;
fast = fast->next->next;
if(slow==fast)
{
fast = head;
while(slow!=fast)
{
slow = slow->next;
fast=fast->next;
}
return slow;

}
}
return NULL;
}

Accepted Answer

Outer And Inner Loop

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.

Space Complexity: O(1)Explanation:

O(1).

Constant space is used.

Time Complexity: O(1)Explanation:

O(N*N), where N is the total number of nodes.

For every iteration of outer-loop, we are iterating the linked-list again.

Accepted Answer

Look Up Table Approach

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.

Space Complexity: O(1)Explanation:

O(N), where N is the total number of nodes.

At most we will put all the N nodes into the look up table.

Time Complexity: O(1)Explanation:

O(N), where N is the total number of nodes.

We would be visiting every node once, as soon as we encounter a multiple visit on a node, then we will stop execution.

Accepted Answer

Slow And Fast Pointer Approach

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.

Space Complexity: O(1)Explanation:

O(1).

Constant space is used.

Time Complexity: O(1)Explanation:

O(N), where N is the total number of nodes.

If a cycle is not present then the fast pointer will reach ‘NULL ’in O(N / 2) time and if there is a cycle then the fast pointer will meet the slow pointer in a maximum of O(N) time. Hence the complexity will be O(N).

You have given a Singly Linked List of integers, determine if it forms a cycle or not.

A cycle occurs when a node's next points back to a previous node in the list. The linked list is no longer linear with a beginning and end—instead, it cycles through a loop of nodes.

Note: Since, it is binary problem, there is no partial marking. Marks will only be awarded if you get all the test cases correct.

Input format :

Output format :

Constraints :

Note :

Top PayPal Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in PayPal Software Engineer