This is the 8th day of my participation in the August More Text Challenge. For details, see:August is more challenging

If you want to keep writing, write a series. What can I write about? Program = algorithm + data structure, which shows the importance of algorithm. This series of old poems tries to explain the algorithm clearly in the simplest language, from shallow to deep, if you are interested, you can pay attention to the column.

The last two articles have written the basic operation of the list, including new list, insert list node, delete list node, query list node and so on. Then the last article wrote about how to tell if a linked list has a loop. Now let’s think a little bit more deeply about how to find the entry to the list. There will also be interviewers will ask about the interview.

Fast and slow pointer judgment method

We can deduce by mathematical formula that the distance A from head to the entry point of the linked list is the same as the distance from the meeting point of Slow and fast to the entry point. Those of you who are interested in this can check it out for yourself. For those of you who are not interested in testing this, remember this conclusion.

The source code to achieve

Node* findLoopStart(Node *head) {Node* fast, *slow; slow = fast = head ; while (slow ! = NULL && fast -> next ! = NULL) { slow = slow -> next ; fast = fast -> next -> next ; if (slow == fast) break ; } if (slow == NULL || fast -> next == NULL) return NULL ; Node * ptr1 = head; // Node * ptr2 = slow; // while (ptr1! = ptr2) { ptr1 = ptr1 -> next ; ptr2 = ptr2 -> next ; } return ptr1 ; // Find the entry point}Copy the code

The above code first uses the speed pointer to determine whether there is a ring. If there is no ring, it returns null. If there is a ring, it continues.

Using the fast and slow Pointers, we can figure out where they meet. All that remains is for the slow pointer at the point where pTR1 =head and ptr2 meet to continue moving forward. Because the point where they meet is the entry point of the ring.

To learn more algorithm problems, or to more project source code, please move to the public number: poetic code.

Now that I’m in, it’s not easy to be original. Let’s go with a “like”.