Make writing a habit together! This is my first day to participate in the “Gold Digging Day New Plan · April More text challenge”, click to see the details of the activity.

Twitter 🤥

Hello everyone, I’m Pan Xiao ‘an! A forever on the road to weight loss front er🐷!

Recently set a algorithm for yourself to practice every day, in line with the “alone le than the lele” share the spirit and deep understanding and practice of feynman learning method need (not only to the nuggets stock), I decided to record every day once every classic algorithm problem of their thinking, with simple, popular and interesting language to each topic clear. Let’s get started

Serving 🥬

Given the head node of a list, return the first node where the list begins to loop. Returns NULL if the list is loopless.

Watch its color smell its taste 🐽

First, leave your hands alone and examine each of the key information in the question. Combining examples, we can have the following key information:

  • Linked lists may not have rings and do not return NULL
  • If you have a ring, you return the node that entered the ring

So here’s the question:

  • How do we tell if a linked list has rings?
  • A linked list with rings how do we know what the entry point is?

Using the Map

We can iterate through the list and use the map to store each node we walk through. When we reach the entry of the loop section, the map will be hit, which will return directly, or if there is no loop, we will iterate over the null at the end of the list.

Double pointer

Double pointer is a frequent problem in linked list. Double pointer, as its name implies, is a method of traversing the target by using two variables to represent two Pointers. In this problem, we use a fast pointer and a slow pointer to traverse the linked list and judge whether the list has a ring. If there is no ring, the fast pointer will traverse to null. The question is how to get the point that enters the ring if there is a ring.

Before we think about that, let’s do a life scenario:

When you were in college, you ran to the playground from your dormitory. Because you often took part in physical exercise, you could not run at a speed of 2m/s. Your roommate is a nerd, and his running speed is 1m/s.

Isn’t it a bit abstract? It doesn’t matter. Let’s draw a picture to understand:

You and your roommate leave the dormOGo past the entrance of the playgroundtAfter o ‘clock, run run run you’ll be inmRun into your roommate. We know that your velocity is zero2m/sThe roommate’s speed is1m/sIt’s 400 meters around the playground. So thistHow far is the entrance to the playground from the dormitory? And to figure that out, we need to figure out whymPoints.

Let’s think about it another way: if you didn’t start in your dorm room, you started at t-point, and the two of you were running a lap, theoretically you would meet at T-point again, and you would pass your roommate exactly one lap. Then why did you meet at m? Because you ran all the way from the dorm to the playground.

  • If the distance from the dormitory to the playground entrance is 400 meters, where is the point M? Is that the entrance to the playground? You huffed and puffed your way to the entrance of the playground for 400 meters, and your roommate was halfway there, and when you finished the lap, your roommate showed up just outside the playground.

  • If the distance from the dormitory to the playground entrance is 100 meters, where is the point M? Is it one hundred meters counterclockwise from the entrance of the playground? Because when your roommate is at the entrance to the playground, you are already 100 meters away from the entrance, which means you jumped the gun 100 meters, and the meeting place is 100 meters earlier.

  • What if the distance from the dormitory to the playground entrance is 500 meters? Where were you when your roommate reached the playground crossing 500 seconds after you started? You’ve done one lap and 100 meters, and then it’s back to the second situation.

If you usexIs the distance from the dormitory to the entrance of the playground, usedyRepresents the clockwise distance from the entrance to the point of encounter, usedzRepresents the remaining distance from the encounter point to the entrance, and we can conclude that:x = n(y+z) - y

N is the number of laps run, and the formula is, the distance from the dormitory to the entrance to the playground is equal to the number of laps run minus the distance clockwise from the entrance to the encounter point, and when n is equal to 1, x is equal to z, which is our case two. When n is equal to 2, which is really case 3, your roommate just got to the starting point, and you’ve already done more than one lap.

So the question is: How do we figure out this z and x?

The answer is: magic. That very day, on the playground, when you catch up with your roommate at m, your roommate suddenly morphs into a dark magician, teleporting you back to your dorm room, giving you a weak, and continuing to run. You’re weakened, you slow down to 1 meter per second, you think, you’ve been hacked, I need to get back to the field, so you run back to the playground, and no surprise, no doubt, you’ll meet again at the playground entrance.

So with that said, let’s go back to our problem, let’s have a fast pointer and a slow pointer, one that moves two nodes at a time, one that moves one node. If the linked list has a ring, the fast and slow nodes will meet at the point M in the ring. At this time, the distance from M to the entry point T, and the distance from the starting point to the entry point T, are in accordance with the formula we deduced above. In the first encounter, reset the fast pointer to the starting point, and keep a constant speed forward with the slow pointer, when they meet again, it is the entry point.

The chopsticks 🥢

The map method

var detectCycle = function (head) {
    let map = new WeakMap(a)while(!!!!! head) {if (map.get(head)) {
            return head
        } else {
            map.set(head, true)
            head = head.next
        }
    }
    return null
};
Copy the code

Double pointer method

var detectCycle = function(head) {
    if(! head || ! head.next)return null;
    / / your roommate
    let slow =head.next;
    / / you
    let fast = head.next.next;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        // You catch up with your roommate at m
        if(fast == slow) {
            // You are hit by black magic, teleported and slowed down
            slow = head;
            while(fast ! == slow) { slow = slow.next; fast = fast.next; }// Meet again
            returnslow; }}// There is a wormhole in the middle of the playground
    return null;
};
Copy the code

The small voice BB 🤫

That’s all about circular linked List II. Now it is 23:35, April 02, 2022 Beijing time, the Qingming Holiday is about to begin, and I have also started my full attendance plan for April. The third phase of the mysterious organization training camp will also start, and the epidemic in Shenzhen has been controlled. However, the epidemic situation in Shanghai seems to be a little out of control, with all kinds of rumors and negative news flying everywhere.

(Thanks to the pillow for sharing this photo)

Shanghai friends hold on! Come on, Shanghai! Come on China!

🎉 if you think this article is helpful to you, please give your thumbs up ~🎉

If you have any questions or suggestions about the wording, knowledge and format of the article, please leave a comment ~🎉