preface

For our algorithm xiaobai, the direct dry topic must be a bit of a puzzle, here I slightly add visual thinking, do not like spray.

Answer:

Title: 141. Circular list – You are given a head node of the list, head, to determine whether there are rings in the list.

Image description is as follows:

First of all, this is the only point to a singly linked list, with the chain table set up a runway, party a and party b two people from the same starting point head with double speed and double speed running on (assuming a step 1, a node b 1 step two nodes), if party a and party b have been ran down to be able to meet again, then illustrate the runway ring, run faster if encountered null point of b, That means there are no rings;

Mix in logical parsing:

  1. Head not null =”if(! head) return false;
  2. Same starting point head start =”let pre = head, cur = head;
  3. If you want to keep running, you have to make sure that fast b doesn’t encounter null =.while(cur && cur.next)(Cur. next ensures that B can run successfully in every step. If he reaches null in cur.next, the race will end early.)
  4. Pre stands for slow a 1 times faster =pre = pre.next
  5. Cur means fast, twice as fast =cur = cur.next.next
  6. In the case of continuous running, if a and B run to the same node address (pre === cur), it means that a and B have met and the linked list has a ring =.if(pre === cur) return true;
  7. If party A and Party B cannot run all the way, i.e. party B reaches the null point first, then the match ends =return false;

Var hasCycle = function(head) {

if(! head) return false; let pre = head,cur = head; while(pre && cur && cur.next){ pre = pre.next; cur = cur.next.next; if(pre === cur) { return true; } } return false;Copy the code

};