Problems/Fast and Slow Pointers/Linked List Loop
Fast and Slow Pointers
easy

Linked List Loop

Detecting cycles in linked lists is a classic problem. It showcases your ability to work with pointer manipulation and algorithmic thinking under memory constraints.

linked-listcycle-detectionfloyd's-algorithmtwo-pointers

Problem Statement

Given the head of a singly linked list, determine whether the linked list contains a loop. A loop is present if any node in the list can be reached again by continuously following the 'next' pointer. Return True if a loop exists; otherwise, return False.

Example 1
Input: A linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (loop back to 3)
Output: True
The linked list contains a cycle, as starting from node 3, you can traverse back to node 3.
Example 2
Input: A linked list: 7 -> 8 -> 9 -> 10 -> null
Output: False
The linked list does not contain a cycle; it terminates at node 10.
Constraints
  • -The number of nodes in the list is in the range [0, 10000].
  • -Node values are integers.
  • -You must solve this problem using O(1) (i.e. constant) memory.

Brute Force Approach

The brute-force approach involves using a data structure like a set to keep track of visited nodes. As you traverse the linked list, check if the current node exists in the set. If it does, you've found a cycle. This is like leaving breadcrumbs as you explore a maze; if you step on a breadcrumb you've already laid, you know you're in a loop. This approach takes O(n) time and O(n) space.

TimeO(n)
SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem