[force buckle] ring list II

142. Circular list II - Power button （LeetCode）

subject ：

Given the head node of a linked list  head , Return to the first node of the link where the list begins to enter .  If the list has no links , Then return to  null.

Ideas ：

Use the speed pointer

Code ：

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

expand ：

1、slow One go 1 Step ,fast One go 2 Step , Can you catch up with me ？

answer ： You can definitely make it , hypothesis slow Enter the cycle and fast The distance to N,fast Two steps at a time ,slow One step at a time , Every time fast and slow The distance will -1,N Next time ,fast and slow The distance is 0.

2、slow One go 1 Step ,fast One go 3 Step , Can you catch up ？fast One go 4 Step ,n Step ？

answer ： not always , hypothesis slow Enter the cycle and fast The distance to N, every time fast and slow The distance will -2, If N If it is not a multiple of two ,fast and slow The distance cannot be 0.

3、 Prove the above method of finding the circulation entrance .

Set the distance before entering the cycle as l

The entrance to fast and slow The distance of the meeting point is x

The length of one cycle is c

slow The length traveled ： l+x

fast The length traveled ： l + nc+x

fast The walking length is slow Of 2 times

2（l+x） = I+x +nc

l = nc -x  

l = (n-1)*c + c-x

therefore l = c-x

4、 Other solutions

  When fast and slow After encounter , Disconnect the cycle , It becomes the problem of finding the intersection of two linked lists