BL
U

60. Detect Cycle in Linked List

Easy

Problem Description

Given a linked list representation where the tail connects back to the 0-based node index pospos (or -1 if no cycle), determine whether a cycle exists using Floyd's cycle-finding algorithm.

Input Format

  • •Line 1: Two space-separated integers NN and pospos (1≤N≤1051 \le N \le 10^5, −1≤pos<N-1 \le pos < N).
  • •Line 2: NN space-separated integers.

Output Format

Print true if a cycle exists, else false.

Example 1:
Input:
4 1
3 2 0 -4
Output:
true
Explanation: Tail connects back to node at index 1; cycle exists.
Example 2:
Input:
2 0
1 2
Output:
true
Explanation: Tail connects to index 0; cycle exists.
Example 3:
Input:
1 -1
1
Output:
false
Explanation: No cycle (pos = -1).
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online