Their thinking

So the problem is to find where the circular list goes into the loop

  1. First determine whether the linked list is a circular list
  2. And then I want to find where I’m going into the ring

Set:

  • Let the length of the outer ring of the list be A
  • After the slow pointer enters the ring, it travels a distance of B to meet fast
  • The fast pointer has completed n cycles of the ring
Head - a - entry - b - meet position | | | -- -- -- -- -- -- -- -- -- -- - | cCopy the code

slow: a + b fast: a + b + n * (b + c) => a + ( n + 1 ) * b + n * c

Since the fast pointer goes twice as long as the slow pointer:

A + + n (n + 1) * b * c = 2 * (a + b) ⟹ a = c + (n – 1) (b + c)

We know that b + c is the length of the ring, which cancels out: A = c

So we know that the distance from the starting point to the entrance is equal to the distance traversed backwards from the meeting point to the entrance

code

var detectCycle = function(head) { if (! head) return null; let fast = slow = head; while (fast && fast.next) { fast = fast.next.next; slow = slow.next; If (fast == slow) {let pre = head while (pre! == slow) { pre = pre.next; slow = slow.next; } return pre; }} return null;Copy the code