Circular linked list

The end of the list is not an empty address, but a node in the list, called a circular list.

Idea 1: fast and slow pointer

For example: a = 1->2->3->4->5->2 (this is the second 2 in the list). The fast pointer takes two steps and the slow pointer takes one step.

  1. Slow =2, fast =3
  2. Slow =3, fast =5
  3. Slow =4, fast =3
  4. Slow =5, fast =5

At this point, after four moves, the fast and slow hands meet. Can get the current ring list.

Idea 1: JS code implementation

var hasCycle = function(head) {
  if(! head)return false;// If the list is empty, return false
  let p = head;/ / pointer to slow
  let q = head;/ / pointer
  while (q && q.next) { // Check whether the list and the next bit of the list node exist, if there is a value to continue the loop
    p = p.next;// Take a slow step
    q = q.next.next;// Take two quick steps
    if(q === p) return true;// If the fast and slow Pointers are equal, the list has a loop.
  }
  return false;// If q or q.next is empty, the list has no loops
};

Copy the code