“This is the 19th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

This paper presents a basic but typical algorithm that reflects the idea of fast and slow Pointers: circular linked lists

The fast and slow pointer is a kind of double pointer, used to judge whether the linked list has closed loop, very good ~ blunt ヾ(◍°∇°◍) Blue ゙

Topic:

Give you the head node of a linked list and check if there are rings in the list.

If there is a node in the list that can be reached again by following the next pointer continuously, then there is a ring in the list. To represent the rings in a given list, the metric system internally uses the integer POS to represent where the tail of the list is connected to in the list (the index starts at 0). Note: pos is not passed as an argument. Just to identify the reality of linked lists.

Returns true if there are rings in the list. Otherwise, return false.

Example 1: input: head = [3,2,0,-4], pos = 1 output: true explanation: there is a ring in the linked list whose tail is connected to a second node.Copy the code

Example 2: input: head = [1,2], pos = 0 output: true explanation: there is a ring in the linked list whose tail is connected to the first node.Copy the code

Example 3: Input: head = [1], pos = -1 Output: false Explanation: There are no loops in the linked list.Copy the code

The way to solve the problem is: fast or slow pointer.

Fast and slow Pointers, as the name suggests, use Pointers with different speeds (used on linked lists, arrays, sequences, etc.) to solve some problems.

These issues mainly include:

Handles problems on rings, such as circular lists, circular arrays, etc. When you need to know the length of a linked list or information at a particular location. The fast and slow pointer algorithm proves that they must meet, and the fast pointer will catch up with the slow pointer;

You can think of it as running on the playground, where the fast ones run in circles and the slow ones run.

Generally, fast is used to define fast Pointers and slow is used to define slow Pointers. Different speed means that fast takes more steps each time and slow takes fewer steps. The general setting is 2 steps for fast and 1 step for slow.

Of course, it is also possible to set it to other integers, such as 3 steps for fast and 1 step for slow.

JavaScript implementation:

/** * @param {ListNode} head * @return {Boolean} */ var hasCycle = function(head) {// let slow = head; let fast = head; // Stop while (fast && fast. Next) {// Slow = slow. Next; fast = fast.next.next; If (slow == fast) {return true; }} // no loop return false; };Copy the code

In addition: also provides a magic solution: O (￣▽￣)d

That is:

var hasCycle = function (head) {
    try {
        JSON.stringify(head)
    } catch{
        return true
    }
    return false
};
Copy the code

The principle is:

Json.stringify does not work properly if the JavaScript object itself contains circular references, error message:

VM415:1 Uncaught TypeError: Converting circular structure to JSON

OK, that’s it

I’m Nuggets Anthony, output exposure input, technical insight into life, goodbye ~