Coding Interview PatternsLinked List Cycle II
MediumFast and Slow Pointers

Linked List Cycle II

Explanation & Solution

Practice Problem

Description

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

A cycle exists if some node in the list can be reached again by continuously following the next pointer. Internally, pos denotes the index of the node that the tail's next pointer connects to (0-indexed). If pos is -1, there is no cycle. Note that pos is not passed as a parameter — it is only used to build the linked list for testing.

Return the value of the node where the cycle starts, or "null" if there is no cycle.

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

Output: 2

Explanation: There is a cycle where the tail node (-4) connects back to the node at index 1 (value 2). The cycle starts at the node with value 2.

Constraints

  • The number of nodes in the list is in the range [0, 10⁴]
  • -10⁵ <= Node.val <= 10⁵
  • pos is -1 or a valid index in the linked list

Approach

Fast and Slow Pointers pattern

1. Initialize Two Pointers

  • Set slow to head
  • Set fast to head
  • Both pointers start at the beginning of the linked list

2. Phase 1 — Detect the Cycle

  • Loop while fast is not null and fast.next is not null
  • Move slow forward by one step: slow = slow.next
  • Move fast forward by two steps: fast = fast.next.next
  • If slow === fast, a cycle has been detected — proceed to Phase 2
  • If the loop exits without meeting, there is no cycle — return null

3. Phase 2 — Find the Cycle Start

  • Reset slow back to head
  • Move both slow and fast forward by one step at a time
  • The node where they meet is the start of the cycle
  • Return slow.val (the value at the cycle start node)

4. Why Does Phase 2 Work?

  • Let the distance from head to the cycle start be a
  • Let the distance from the cycle start to the meeting point be b
  • Let the remaining cycle length be c (so the full cycle is b + c)
  • When they first meet: slow traveled a + b, fast traveled a + b + (b + c) = a + 2b + c
  • Since fast moves twice as fast: 2(a + b) = a + 2b + c → a = c
  • So moving one pointer from head and one from the meeting point, both at speed 1, they meet at the cycle start

Key Insight

  • This is the second phase of Floyd's Cycle Detection algorithm
Time
O(n)both phases traverse at most the full list
Space
O(1)only two pointer variables are used

Visualization

Input:
Linked List Traversal
—
302102-43

Press play to start traversal

Slow (S)Fast (F)Both
8 steps

Solution Code

Previous
Linked List Cycle
Next
Middle of the Linked List