There are many algorithms on the web about circular lists, but I believe that not everyone can understand them thoroughly. I’m going to deduce it for you here, and I believe that with an understanding of the following process, I can guarantee that you are never afraid to find algorithms for circular lists, keep them in mind, and keep them constant.

No more nonsense, first code:

import java.util.*;

class Program {
  public static LinkedList findLoop(LinkedList head) {
    LinkedList slow = head.next;
    LinkedList fast = head.next.next;

    while(slow ! = fast){ slow = slow.next; fast = fast.next.next; }// If slow and fast have the same value, it indicates that they meet in the circular list. In this case, move the fast pointer to the head node.
    fast = head;
    while(slow ! = fast){ fast = fast.next; slow = slow.next; }return fast;
  }

  static class LinkedList {
    int value;
    LinkedList next = null;

    public LinkedList(int value) {
      this.value = value; }}}Copy the code

The code is pretty simple, but to see why the end of the second while loop gives you the beginning of the list, listen to me. Be sure to look closely at the diagram and follow my text:

Several variables in the graph illustrate:

  • DThe variable represents where the head node -> ring node begins.
  • PThe variable represents the step length of Slow in the circular linked list when the slow node meets the fast node.
  • RThe variable represents how many steps a slow node has left to reach the beginning of the circular list.
  • TThe variable represents the total length of the list.

The conclusion that T = D + R + P can be reached by using the variables in the figure, but it seems that the problem cannot be solved at present. The most important thing is the R variable. How to make the slow node go through the R variable and stop to get the starting position of the ring? Let’s move on!!

Given that the step size of slow is 1 and the step size of the fast node is 2, assuming slow = x, then fast = 2x

It is known that the step size of a slow node is D + P, so slow = X = D + P, fast = 2X = 2D + 2P

The fast node goes one P further than the slow node, so T = 2D + P continues to be obtained

Now there are two conclusions for the T variable, T = D + R + P and T = 2D + P

So if I drop the P variable, I get D plus R is equal to 2D, which is D plus R is equal to D plus D, and I drop another D variable, and I get D is equal to R. That is, two Pointers, one of which covers the distance D, the other must cover the distance R, and the R distance must stop at the beginning of the ring.

That’s why we move the fast pointer to the head. The fast and slow Pointers both move in step size 1, with fast going D distance and slow going R distance, so when they’re all done and the value is the same, that’s where the loop starts.

The end of the flower 🎉, there are small partners do not understand the place can be discussed together oh, we grow up together progress.