TIC
The Interns Company

Linked List Cycle

EasyAcceptance: 45.8%
Hash TableLinked ListTwo Pointers

Problem Statement

Given 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
  • pos is -1 or a valid index in the linked-list

Input Format:

  • The head of a linked list
  • pos denotes the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle.

Output Format:

  • Return true if there is a cycle in the linked list. Otherwise, return false.

Examples:

Example 1:

Input:

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

Output:

true

Explanation:

There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input:

head = [1,2], pos = 0

Output:

true

Explanation:

There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input:

head = [1], pos = -1

Output:

false

Explanation:

There is no cycle in the linked list.

Solutions

Floyd's Cycle-Finding Algorithm (Tortoise and Hare)

Time: O(n)
Space: O(1)

Use two pointers, a slow-moving pointer and a fast-moving pointer. If they ever meet, there's a cycle.

Hash Table Approach

Time: O(n)
Space: O(n)

Keep track of visited nodes using a hash set. If we encounter a node we've seen before, there's a cycle.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Create the linked list: 3 -> 2 -> 0 -> -4 -> (back to 2)
  2. Initialize slow = head (node with value 3), fast = head (node with value 3)
  3. Iteration 1:
  4. Move slow to next node: slow = node with value 2
  5. Move fast two steps: fast = node with value 0
  6. slow != fast, continue
  7. Iteration 2:
  8. Move slow to next node: slow = node with value 0
  9. Move fast two steps: fast = node with value 2 (cycled back)
  10. slow != fast, continue
  11. Iteration 3:
  12. Move slow to next node: slow = node with value -4
  13. Move fast two steps: fast = node with value -4
  14. slow == fast, we've detected a cycle
  15. Return true

Hints

Hint 1
Consider using two pointers, one moving twice as fast as the other. What happens if there's a cycle?
Hint 2
If there is no cycle, the fast pointer will reach the end of the list.
Hint 3
If there is a cycle, the fast pointer will eventually meet the slow pointer.

Video Tutorial

Linked List Cycle - Floyd's Tortoise and Hare Algorithm

YouTube•Learn the Linked List Cycle solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the slow and fast pointers moving through the linked list, with the slow pointer moving one step at a time and the fast pointer moving two steps at a time.

Key visualization elements:

  • slow pointer
  • fast pointer
  • cycle detection

Asked By

AmazonMicrosoftBloombergFacebookGoogleAdobeAppleOracle

Implementation Notes

This is a classic problem that tests understanding of linked list traversal and cycle detection. Floyd's Cycle-Finding Algorithm (also known as Tortoise and Hare algorithm) is an elegant solution with O(1) space complexity.