Cycle Detection in a Singly Linked List
Posted: 10 Dec, 2019
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.
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
Try to solve this problem in O(N) Time Complexity and O(1) space Complexity
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.
Ninja And The List
Posted: 19 Jan, 2022
Insertion In Circular Linked List
Posted: 21 Apr, 2022
Insertion In A Singly Linked List
Posted: 22 Apr, 2022
Deletion In Doubly Linked List
Posted: 22 Apr, 2022
Insertion In Doubly Linked List
Posted: 24 Apr, 2022