Circular linked list OJ question

Catalog

The first step ： Circular list I

Higher order ： Circular list II

Additional improvement problems

---

The first step ： Circular list I

subject

Ideas

Follow up and problems , Use fast and slow pointer method , Slow pointer one step , Let's go two steps .

Because considering that the number of linked list nodes may be odd or even , So the fast pointer goes to null or the next node of the fast pointer is null , It proves that the linked list is acyclic .

If there are rings , Fast pointer advanced ring , When the slow pointer enters the loop, it is assumed that the fast pointer is different from the slow pointer N, Then each time it is one step faster than full , The difference distance between fast and slow pointers is N,N-1, N-2, ... 2, 1, 0. When the distance is 0 when , That is to meet . And slow a step fast Two steps ,fast I'm sure I can catch up with slow.

Code

bool hasCycle(struct ListNode *head) 
{
    struct ListNode* slow, * fast;
    slow = fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)// Note here that the address of the comparison node must be the same when comparing 
        {
            return true;
        }
    }
    return false;
}

Higher order ： Circular list II

subject

Ideas

obviously , This is an upgraded version of the catch-up problem , Still use the fast and slow pointer solution .

In the last question , We can judge whether the linked list has rings , And you can find the linked list , The node location where the fast and slow pointers meet . In this question , We need to use the node where the fast and slow pointers meet .

Here we use ：

slow Represents slow pointer

fast Represents the fast pointer

meet Represents the position where the speed pointer meets

Give a conclusion first ：L = C - X

explain ：( Mathematical analysis )

slow And fast The distance traveled by the two pointers when they meet    slow： L+X

                                                            fast：L+nC+X

fast The journey is slow Double of . therefore 2*(L+X) = L+nC+X

Simplify ：L = nC - X

Arrange this formula ：L = C * (n - 1) - (C - X)

Be careful ：C*(n-1) It has no effect on the conclusion , Now let the outer ring head One step at a time , Inside ring meet One step at a time ,

When there is no ring outside the ring , The ring will only go round , But in the end, when the node outside the ring enters the ring , The inner ring will meet the outer ring at the node just entering the ring

Code

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

Additional improvement problems

This kind of circular linked list , We use fast and slow pointers , You will find that it's all for slow Take a step ,fast Take two steps .

problem ：

If slow Take a step ,fast Take three steps or fast Take four steps , Is that OK ？ Is it more efficient ？

answer ：

Only by slow Take a step ,fast Take two steps , Other methods are not allowed .

explain ：

hypothesis fast And slow The difference distance is N, The difference distance is 0 Then meet

slow a step ,fast Two steps ,fast One step at a time .

fast And slow Change of phase difference distance ：N,N-1,N-2,...,2,1,0.

slow a step ,fast The three step ,fast Two steps at a time .

fast And slow Phase difference distance N The change of ：

If N For the even ：N,N-1,N-2,...,2,1,0, Can meet

If N It's odd ：N,N-2,N-4,...,3,1,-1, This round cannot meet

So if N It's odd , But this round cannot meet , A few more rounds ？ Is it possible to catch up ？

answer ：

This depends on the situation ,fast And slow Phase difference distance N by -1 Time description fast stay slow Previous , The difference distance is N-1

If N-1 Is odd ( Equal to the circumference of the ring is an even number ) It's in a dead cycle , Every cycle is N,N-2,N-4,...,3,1,-1

If N-1 It's even ( Equivalent to the circumference of the ring is an odd number ) Then we can catch up in the second round .

Other situations are like this .