Skip to main content

141. Linked List Cycle

easy

Detect whether a singly linked list contains a cycle. Floyd's tortoise-and-hare algorithm answers in O(n) time with constant space — the textbook two-pointer-speeds technique.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Return true if there is a cycle in the linked list. Otherwise, return false.

Constraints

  • The number of the nodes in the list is in the range [0, 10^4].
  • -10^5 <= Node.val <= 10^5

Examples

Example 1

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

Explanation: There is a cycle where the tail connects back to the node at index 1.

Example 2

Input
head = [1,2], pos = 0
Output
true

Example 3

Input
head = [1], pos = -1
Output
false

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

A hash set of visited nodes works — O(n) time and O(n) space.

Hint 2

Can you do it in O(1) extra space?

Hint 3

Floyd's: slow moves one step, fast moves two. If there's a cycle they'll eventually meet. If fast reaches null, there's no cycle.

Solution approach

Reveal approach

Floyd's tortoise-and-hare. Initialize slow = head and fast = head. Loop while fast and fast.next are both non-null: advance slow by one and fast by two. If slow == fast at any point, there's a cycle — return true. If the loop exits, fast hit the end — no cycle, return false. Works because in a cycle of length L, the fast pointer gains one step per iteration relative to the slow one and must eventually catch up. O(n) time, O(1) extra space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • two-pointers
  • floyds-cycle

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Meta
  • Bloomberg

More Linked Lists practice problems

See all Linked Lists problems →