AlgoMaster Logo

Linked List Cycle II

Last Updated: April 1, 2026

medium
4 min read

Understanding the Problem

This is a two-part challenge. First, you need to detect whether a cycle exists in the linked list. Second, and this is the harder part, you need to find exactly where the cycle starts.

A cycle means that some node's next pointer points back to a previous node in the list, creating a loop. If you just keep following next pointers, you would loop forever. The question is: which node is the entry point of that loop?

The naive thought is to track which nodes you have visited. If you visit a node twice, that is where the cycle begins. But the follow-up asks for O(1) memory, so we need something cleverer. This is where Floyd's cycle detection algorithm comes in, and the mathematical proof behind it is what makes this problem a classic.

Key Constraints:

  • 0 <= n <= 10^4 → Up to 10,000 nodes. Both O(n) and O(n^2) approaches would pass, but the follow-up pushes us toward O(n) time with O(1) space.
  • -10^5 <= Node.val <= 10^5 → Node values are not unique. Two different nodes can have the same value, so you cannot use values alone to identify the cycle start. You need to track node references (addresses), not values.
  • pos is -1 or valid index → The input is well-formed. If there is a cycle, pos points to a valid node. We do not need to worry about malformed inputs.

Approach 1: Hash Set

Intuition

The most natural approach: as you traverse the linked list, keep track of every node you have visited. The first node you encounter for the second time must be where the cycle begins, because that is the point where the list loops back.

A hash set gives us O(1) lookup for checking whether we have seen a node before. We store node references (not values, since values can repeat) and check each node against the set as we go.

Algorithm

  1. Create an empty hash set to store visited node references.
  2. Start at the head and traverse the linked list.
  3. For each node, check if it is already in the set.
  4. If yes, return that node. It is the cycle start.
  5. If no, add it to the set and move to the next node.
  6. If you reach null, there is no cycle. Return null.

Example Walkthrough

1Start: current = node 3 (index 0), seen = {}
3
current
2
0
-4
null
1/6

Code

This approach works but uses O(n) extra memory. Can we detect the cycle start using only pointer manipulation, without remembering every node?

Approach 2: Floyd's Tortoise and Hare (Optimal)

Intuition

This is one of those algorithms where the "aha moment" comes from a mathematical observation. Floyd's algorithm uses two pointers: a slow pointer that moves one step at a time, and a fast pointer that moves two steps at a time. If there is a cycle, the fast pointer will eventually catch up to the slow pointer inside the cycle.

But detecting the cycle is only half the problem. The real insight is what happens after the two pointers meet. Suppose the distance from the head to the cycle start is a nodes. The distance from the cycle start to the meeting point is b nodes. The remaining distance in the cycle (from the meeting point back to the cycle start) is c nodes. So the cycle length is b + c.

When the slow pointer reaches the meeting point, it has traveled a + b steps. The fast pointer has traveled 2(a + b) steps. But the fast pointer has also completed some number of full loops around the cycle. So: 2(a + b) = a + b + k(b + c). Simplifying: a + b = k(b + c), which means a = (k - 1)(b + c) + c. The critical result: a = c (plus some full cycles). The distance from the head to the cycle start equals the distance from the meeting point to the cycle start.

So after the two pointers meet, if we reset one pointer to the head and keep the other at the meeting point, then advance both one step at a time, they will meet at the cycle start.

Algorithm

  1. Initialize slow and fast both pointing to head.
  2. Move slow one step and fast two steps at a time.
  3. If fast reaches null, there is no cycle. Return null.
  4. If slow and fast meet, a cycle exists.
  5. Reset slow to head. Keep fast at the meeting point.
  6. Move both pointers one step at a time.
  7. When they meet again, that node is the cycle start. Return it.

Example Walkthrough

1Phase 1: slow=3(idx 0), fast=3(idx 0)
slow
3
fast
2
0
-4
null
1/6

Code