This is the seventh 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 article wrote the basic operation of the list, including new list, insert list node, delete list node, query list node and so on. Now this article is about how to determine whether a linked list has a loop algorithm. This question is quite common in the interview.

Fast and slow pointer judgment method

For this problem we can use the “fast slow pointer” method. Slow = slow->next; fast = fast->next->next Since FAST moves faster than slow, if there is a loop, FAST will enter the loop first, while slow will enter the loop later. When both Pointers are in the loop, after a finite number of operations, the fast and slow Pointers must meet.

The specific code is as follows:

Bool exitLoop(Node *head) {Node *fast, *slow; slow = fast = head ; while (slow ! = NULL && fast -> next ! = NULL) { slow = slow -> next ; fast = fast -> next -> next ; if (slow == fast) return true ; } return false ; }Copy the code

This is shown in the figure above

That is to say, slow moves forward one step at a time, while FAST moves forward two steps, so the distance between FAST and Slow is shortened by one step after each step operation. In this way, the distance between fast and Slow will gradually shrink:… 5, 4, 3, 2, 1, 0 -> Encounter. In addition, because the distance between fast and slow in the same ring is not greater than the length of the change, slow must not have gone for a week before they meet (or just after they have gone, which occurs at the beginning when fast and slow are both at the entrance 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”.