Ring chain

Circular list

subject

analysis

== Let's dissect the code ==

bool hasCycle(struct ListNode *head) {    struct ListNode* fast = head,*slow = head;    while(fast && fast->next)    {        fast = fast->next->next;        slow = slow->next;        if(fast == slow)            return true;    }    return false;}

Extension problem ：

==1. Why? fast and slow Will meet in the ring , Will there be such a situation . Is always staggered in the ring, never meet ？ Please prove .==

Conclusion ： Just up there fast and slow It must have met

prove ：

First step ：slow and fast,fast It must be an advanced ring , At this time slow yes fast Half the distance before entering the ring .

The second step ： With slow Ring entry ,fast I've been walking in the ring for a while , go How much depends on the size of the ring

The third step ： Let's assume that slow When entering the loop, the distance is the same as fast yes ==N==

slow Every time you go forward 1 Step ,fast Two steps forward , Every chase , Judge the meeting , The result is ==N-1==, In other words, the distance between them is decreasing step by step every time they chase , Until they met

== Another problem arises here is slow And fast As long as the step difference is one, you can meet ==

==2. Why? slow Take a step ,fast Two steps ？fast Can you take more than two steps ？==

Conclusion ：fast go n Step ,n>2, Not necessarily meet

Here is an analysis of slow Take a step ,fast The staggered and non staggered situation of taking three steps

The distance between them changes in pairs at a time , This means that it may be staggered

== The above parity problem arises again N It's their multiple of step difference that they can meet ==

Circular list II

subject

== How to find the entry point of a ring ==

analysis

Let's go straight to the conclusion == A pointer starts from the meeting point , A pointer starts from the chain header , They will meet at the entrance of the ring ==

struct ListNode *detectCycle(struct ListNode *head) {    struct ListNode * fast = head,* slow = head;    while(fast && fast->next)    {                fast = fast->next->next;        slow = slow->next;              if(slow == fast)// meet         {            // Meet node             struct ListNode * meetNode = fast;            while(meetNode != head)            {                meetNode = meetNode->next;                head = head->next;            }            return meetNode;        }          }    return NULL;}