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...
Adobe Software Quality Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
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

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter