Linked List Cycle II

Linked Lists, problem 6 of 10

Linked List Cycle II

Medium

LC #142

fast & slow pointerscycle detection

Not attempted yet

Given the head of a linked list, return the index of the node where the cycle begins (0-based, counting from head), or -1 if the list has no cycle.

Return an index rather than the node, so the answer is a plain number. Each example's pos is the index that the last node's next points back to. Your function receives only head.

Example 1

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

Example 2

Input: head = [1,2], pos = 0
Output: 0

Example 3

Input: head = [1], pos = -1
Output: -1

Constraints

  • 0 ≤ number of nodes ≤ 10⁴
  • -10⁵ ≤ Node.val ≤ 10⁵
  • pos is -1 or a valid index

Can you solve it with O(1) extra space?

Python

Loading draft…

Test results

11 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

3 examples, 8 hidden

Run examples, then submit all tests.