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:
- Head not null =”
if(! head) return false;
- Same starting point head start =”
let pre = head, cur = head;
- 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.) - Pre stands for slow a 1 times faster =
pre = pre.next
- Cur means fast, twice as fast =
cur = cur.next.next
- 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;
- 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
};