Find the entry point of a circular list

If a = 1->3->4->5->6->7->8->5, return 5.

Idea 1: fast and slow pointer positioning

  1. Assume that the head of the list is a distance from the entry point of the list.
  2. When the slow pointer reaches the entry point, the distance of the slow pointer is A, and the distance of the fast pointer is 2A.
  3. Assume that ring for a + x, the length of the pointer to pointer want to catch up with the slow at this time you need x step, namely x wheel, because in a circle, a two step one step, each round to catch up with the step more, so after x wheel speed pointer to meet, meet the current point distance away from the ring at this time is equal to (a) + x – x = a;
  4. It can be deduced that the distance between the head node and the entry point is equal to the distance between the meeting point of the fast and slow Pointers and the entry point. So we loop the head and the encounter down, and when they meet again we find the entry point.

Idea 1: JS code implementation

var detectCycle = function(head) {
  if(! head)return null;
  let p = head; / / pointer to slow
  let q = head; / / pointer
  while (q && q.next) {
    p = p.next;
    q = q.next.next;
    if (q === p) { // indicates that the linked list has a ring and the fast and slow Pointers meet
      let temp = head; // retrieve the header
      while(q ! == temp) {// The header and the encounter take one step at a time.
        q = q.next;
        temp = temp.next;
      }
      return q; // When you get to this line of code, temp and q meet again, which is the entry point.}}return null; // Return null if the list is loopless
};

Copy the code