Cycle Detection in a Linked List
Determine if a given Singly Linked List of integers forms a cycle.
Explanation:
A cycle exists in a linked list if a node's next pointer points back to a previous node, creating a loop instead of reaching the end. In a cyclic linked list, there's no clear beginning or end, but rather a continuous loop of nodes.
Note:
This is a binary problem, meaning you will only receive full marks if all test cases are correct without partial credit.
Input:
The first line for each test case contains the elements of the singly linked list, separated by a single space, and ends with -1. The value -1 will not be an element of the list.
The second line contains an integer 'pos', representing the position (0-indexed) in the linked list where the tail connects to form a cycle. If 'pos' is -1, there is no cycle in the linked list.
Output:
Output "true" if the linked list contains a cycle, otherwise "false".
Note: You are not required to explicitly print the output; this has been handled for you.
Example:
Input:
3 2 0 -4 -1
1
Output:
true
Input:
1 2 3 4 5 -1
-1
Output:
false
Constraints:
- 0 ≤ N ≤ 10^6
- -1 ≤ pos < N
- -10^9 ≤ data ≤ 10^9, data ≠ -1
- 'N' is the number of nodes in the linked list.
- 'pos' indicates the position (0-indexed) where the tail connects to the list.
- 'data' is the integer value of the linked list node.
- Time Limit: 1 second
Note:
Attempt to solve this problem with O(N) time complexity and O(1) space complexity.
AnswerBot
2d
Detect if a singly linked list forms a cycle by checking if a node's next pointer points back to a previous node.
Traverse the linked list using two pointers, one moving at double the speed of the othe...read more
Help your peers!
Add answer anonymously...
Top Adobe Software Quality Engineer interview questions & answers
Popular interview questions of Software Quality Engineer
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app