AlgoMaster Logo

Linked List Cycle II

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

The problem has two parts. First, detect whether a cycle exists in the linked list. Second, find exactly which node the cycle starts at, which is the harder part.

A cycle means some node's next pointer points back to an earlier node, creating a loop. Following next pointers from the head would then run forever. The task is to return the node where that loop reconnects.

Tracking visited nodes solves it directly: the first node you reach twice is the cycle start. The follow-up asks for O(1) memory, which rules out storing every node and points to Floyd's cycle detection algorithm. Detecting a cycle is the easy half; pinpointing where it starts relies on a short distance argument covered in Approach 2.

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

As we traverse the list, we record every node visited. The first node we reach a second time is where the cycle begins, since that is the only node the list loops back to.

A hash set gives O(1) lookup for the "have I seen this node?" check. We store node references rather than values, because two different nodes can share the same value and only the reference identifies a node uniquely.

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 uses O(n) extra memory. The next approach finds the cycle start with only two pointers and no auxiliary storage.

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

Intuition

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 a cycle exists, the fast pointer laps the slow one and they meet inside the cycle. If there is no cycle, the fast pointer reaches the end.

Detection is only half the problem. Finding the start depends on where the two pointers meet. Let a be the distance from the head to the cycle start, b the distance from the cycle start forward to the meeting point, and c the remaining distance from the meeting point back around to the cycle start. The cycle length is b + c.

When the pointers meet, slow has traveled a + b steps and fast has traveled twice that, 2(a + b). Fast also covered some whole number of extra laps k around the cycle, so 2(a + b) = a + b + k(b + c). That simplifies to a + b = k(b + c), and since the cycle length is b + c, to a = (k - 1)(b + c) + c. So a and c differ by a whole number of cycle lengths.

This is what makes the second phase work. Reset one pointer to the head, leave the other at the meeting point, and advance both one step at a time. The head pointer reaches the cycle start after exactly a steps; the meeting-point pointer needs c steps to reach it (plus any full laps, which land it on the same node). Because a and c are equal modulo the cycle length, both pointers arrive at the cycle start on the same step.

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