How do you approach Linked List Cycle?

Since the input includes the position where the cycle connects, the answer can be determined from the pos value.

What is the time complexity of Linked List Cycle?

Time complexity: O(1) - direct check from pos parameter. Space complexity: O(1) - constant space.

What are common mistakes on Linked List Cycle?

Reassigning next before saving it, which loses the rest of the list. Skipping the dummy head, which forces a special case every time the real head changes. Advancing the fast pointer without checking both fast and fast.next - the null dereference only shows up on even-length lists.

gitGood.dev

← Back to problems

Linked List Cycle

EasyData Structures

Description

Given a linked list represented as an array of values and a pos value indicating where the tail connects to (0-indexed), determine if the linked list has a cycle.

The pos parameter indicates the index of the node that the tail's next pointer is connected to. If pos is -1, there is no cycle.

Return true if there is a cycle, false otherwise.

Note: In a real linked list, you would use Floyd's cycle detection. Here, since we have the position, you can determine the answer directly from the input.

Example 1

Input: head = [3, 2, 0, -4], pos = 1

Output: true

Explanation: The tail connects to node index 1, creating a cycle.

Example 2

Input: head = [1, 2], pos = 0

Output: true

Explanation: The tail connects to node index 0, creating a cycle.

Example 3

Input: head = [1], pos = -1

Output: false

Explanation: There is no cycle.

Constraints

- The number of nodes is in the range [0, 10^4]. - -10^5 <= Node.val <= 10^5 - pos is -1 or a valid index in the linked list.

Linked List Cycle: approach, complexity and pitfalls

An easy linked list problem, graded against 8 test cases (5 of them hidden).

The pattern: Linked List

Pointer manipulation - reversal, cycle detection, and merging without extra space.

Reach for it when you see: Any problem handing you a list head, especially with an O(1) space constraint.

If you are stuck

Show the 3-step hint ladder

Since the input includes the position where the cycle connects, the answer can be determined from the pos value.
A cycle exists if and only if pos is a valid index (not -1) and the list is non-empty.
In a real linked list interview, you would use Floyd's tortoise and hare algorithm with slow and fast pointers.

The optimal approach

Show the approach: Position-Based Detection

Since the linked list is represented as an array with a `pos` parameter, a cycle exists if and only if `pos >= 0` and the list has nodes.

In a real linked list implementation, you would use Floyd's cycle detection algorithm (tortoise and hare): use two pointers moving at different speeds. If they meet, there's a cycle.

Floyd's Algorithm (for reference):

- Slow pointer moves 1 step at a time, fast pointer moves 2 steps.

- If there's a cycle, they will eventually meet.

- Time: O(n), Space: O(1).

Time: O(1) - direct check from pos parameter
Space: O(1) - constant space

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Linked List mistakes

These apply to the pattern as a whole, not just this problem.

Reassigning `next` before saving it, which loses the rest of the list.
Skipping the dummy head, which forces a special case every time the real head changes.
Advancing the fast pointer without checking both `fast` and `fast.next` - the null dereference only shows up on even-length lists.

← Back to problems

Linked List Cycle

EasyData Structures

Description

Given a linked list represented as an array of values and a pos value indicating where the tail connects to (0-indexed), determine if the linked list has a cycle.

The pos parameter indicates the index of the node that the tail's next pointer is connected to. If pos is -1, there is no cycle.

Return true if there is a cycle, false otherwise.

Note: In a real linked list, you would use Floyd's cycle detection. Here, since we have the position, you can determine the answer directly from the input.

Example 1

Input: head = [3, 2, 0, -4], pos = 1

Output: true

Explanation: The tail connects to node index 1, creating a cycle.

Example 2

Input: head = [1, 2], pos = 0

Output: true

Explanation: The tail connects to node index 0, creating a cycle.

Example 3

Input: head = [1], pos = -1

Output: false

Explanation: There is no cycle.

Constraints

- The number of nodes is in the range [0, 10^4]. - -10^5 <= Node.val <= 10^5 - pos is -1 or a valid index in the linked list.

Linked List Cycle: approach, complexity and pitfalls

An easy linked list problem, graded against 8 test cases (5 of them hidden).

The pattern: Linked List

Pointer manipulation - reversal, cycle detection, and merging without extra space.

Reach for it when you see: Any problem handing you a list head, especially with an O(1) space constraint.

If you are stuck

Show the 3-step hint ladder

Since the input includes the position where the cycle connects, the answer can be determined from the pos value.
A cycle exists if and only if pos is a valid index (not -1) and the list is non-empty.
In a real linked list interview, you would use Floyd's tortoise and hare algorithm with slow and fast pointers.

The optimal approach

Show the approach: Position-Based Detection

Since the linked list is represented as an array with a `pos` parameter, a cycle exists if and only if `pos >= 0` and the list has nodes.

In a real linked list implementation, you would use Floyd's cycle detection algorithm (tortoise and hare): use two pointers moving at different speeds. If they meet, there's a cycle.

Floyd's Algorithm (for reference):

- Slow pointer moves 1 step at a time, fast pointer moves 2 steps.

- If there's a cycle, they will eventually meet.

- Time: O(n), Space: O(1).

Time: O(1) - direct check from pos parameter
Space: O(1) - constant space

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Linked List mistakes

These apply to the pattern as a whole, not just this problem.

Reassigning `next` before saving it, which loses the rest of the list.
Skipping the dummy head, which forces a special case every time the real head changes.
Advancing the fast pointer without checking both `fast` and `fast.next` - the null dereference only shows up on even-length lists.