Skip to main content

142. Linked List Cycle II

medium

Not just whether a cycle exists — return the node where it begins. The sequel to Floyd's tortoise-and-hare, with the second phase that interviewers love to ask you to derive on the spot.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null. 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. Do not modify the linked list.

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.

Examples

Example 1

Input
head = [3,2,0,-4], pos = 1
Output
tail connects to node index 1

Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2

Input
head = [1,2], pos = 0
Output
tail connects to node index 0

Example 3

Input
head = [1], pos = -1
Output
no cycle

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Phase 1: detect a cycle with Floyd's slow/fast. If fast reaches null, return null.

Hint 2

Phase 2: once slow and fast meet inside the cycle, reset one pointer to head. Move both one step at a time. They'll meet at the cycle entry.

Hint 3

The math: let F = distance head → entry, a = distance entry → meeting point along the cycle, b = remainder of cycle. Slow walked F+a, fast walked F+a+k(a+b). Setting fast = 2·slow yields F = b + (k-1)(a+b), so F steps from head equals (a+b−a) steps from the meeting point, both landing on the entry.

Solution approach

Reveal approach

Floyd's tortoise-and-hare in two phases. Phase 1 (detect): slow = fast = head; loop advancing slow by one and fast by two. If fast or fast.next becomes null, there is no cycle — return null. If slow == fast, a cycle exists and they're meeting somewhere inside it. Phase 2 (locate entry): reset one pointer (say slow2 = head). Advance slow2 and slow one step at a time. The node where they meet is the cycle entry — return it. The math behind phase 2: the distance from head to the cycle entry equals the distance from the meeting point to the entry going forward around the cycle, so walking both at the same speed converges them on the entry. O(n) time, O(1) extra space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • linked-list
  • fast-slow-pointers
  • floyds-cycle
  • two-pointers

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • Google
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Linked List Cycle II and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →