mafeshsho8lmafeshsho8l
Get Started
All coding questions

Linked List Cycle

easy
NeetCode 150linked-listtwo-pointers

Problem

Given the head of a singly linked list, decide whether it contains a cycle, meaning some node's next pointer eventually revisits an earlier node. Use constant extra space.

Examples

Input: 3 -> 2 -> 0 -> -4 with tail linking back to node 2
Output: true
Following next pointers loops forever.
Input: 1 -> 2 with no loop
Output: false
The list terminates at null.

Constraints

  • • 0 <= number of nodes <= 10^4
  • • Solution must use O(1) extra space
Hints(tap to reveal)
  • 1. A slow and a fast pointer move at different speeds.
  • 2. In a cycle the fast pointer eventually laps the slow one.
Optimal approach(spoiler)
  1. Advance a slow pointer one step and a fast pointer two steps per iteration.
  2. If the fast pointer reaches null, there is no cycle.
  3. If the two pointers ever meet, a cycle exists.
  4. This is Floyd's tortoise and hare technique.
  5. O(n) time, O(1) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor