“This is the 12th day of my participation in the November Gwen Challenge. The event details: The Last Gwen Challenge 2021” [TOC]

Link chain

Circular linked list

The title

image-20211025221103012


Analysis of the

image-20211025223634637


image-20211025225530551


Let’s take a look at the code

image-20211025233902707 


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;
}
Copy the code

Extension problem:

1. Why do fast and slow meet in the ring? Is there such a situation? Is in the ring always cross never to meet? Please prove it.

Conclusion: As far as fast and slow are concerned, they must meet

Proof:

Step 1: Slow and fast. Fast is definitely an advanced loop, where slow is half the distance before fast enters the loop.

Step 2: With slow into the ring, FAST has walked in the ring for a period of time, how much to walk depends on the size of the ring

Step 3: We assume that the distance and fast are N when slow enters the loop

Slow takes 1 step forward and fast takes 2 steps forward. For each chase, the result is N-1. That is to say, the distance between them decreases step by step until they meet

image-20211026071344761


Here another problem arises that slow and fast can meet as long as the step difference is one

2. Why take one step slow and two steps fast? Can FAST take more than two steps?

Conclusion: If FAST takes n steps, n>2, it may not meet

Here we analyze the interleaved and uninterleaved situations where a slow takes one step and fast takes three steps

The distance between them is decreasing by two at a time, which means they may cross

image-20211026080439189


And that’s where the odd and even problem comes in: N is a multiple of their step differences

Circular linked list II

The title

image-20211026222807713


How to find the entry point of a ring

Analysis of the

So let’s just jump to the conclusion that one pointer starts at the encounter point, one pointer starts at the head of the chain, and they’ll meet at the entry point of the ring

image-20211026233854511


image-20211026234236282 


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 the node
            struct ListNode * meetNode = fast;
            while(meetNode ! = head) { meetNode = meetNode->next; head = head->next; }returnmeetNode; }}return NULL;
}
Copy the code