A: hi! ~ Hello, everyone, I am YK bacteria 🐷, a front-end microsystem ✨, like to share their small knowledge 🏹, welcome to follow me 😘 ~ [wechat account: YK2012YK2012, wechat official account: ykyk2012]

“This is the third day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.”

141. Circular linked lists

Given a linked list, determine whether 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, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there are no rings in the linked list. Note: POS is not passed as an argument, just to identify the actual state of the linked list.

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

Source: LeetCode link: leetcode-cn.com/problems/li…

【 solution 1 】 Use Map

When we get to four words again, what we think about is we need to remember all the nodes that we walked through before, so that we know when we get to them again. A data structure such as a Map is a natural thought.

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
 * @return {boolean}* /
var hasCycle = function(head) {
    let map = new Map(a)// Iterate over the list
    while(head) {
        // If this node is present in the map, the pointer arrives again and returns true, indicating that there is a ring
        if(map.has(head)) return true
        // Place the node in the map with a value of true
        map.set(head, true)
        // Move the pointer back
        head = head.next
    }
    // If the loop does not return true, there is no loop, so return false
    return false
};
Copy the code

Using a map, the space complexity is a bit high

【 solution 2 】 Fast and slow pointer

Let’s think of it another way. Let’s iterate through the list with two Pointers. A pointer that takes one step at a time is called a slow pointer, and a pointer that takes two steps at a time is called a fast pointer.

Traversing the linked list, if the fast and slow Pointers meet, it means there is a ring, if there is no encounter, it means there is no ring

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
 * @return {boolean}* /
var hasCycle = function(head) {
    let fast = head
    let slow = head
    while(fast){
        if(fast.next === null) return false
        slow = slow.next
        fast = fast.next.next
        if(slow === fast) return true
    }
    return false
};
Copy the code

【 solution 3 】JS characteristics

Finally, we skillfully use THE JS feature to solve this problem

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
 * @return {boolean}* /
var hasCycle = function(head) {
    try{
        JSON.stringify(head)
    }catch(e){
        return true
    }
    return false
};
Copy the code

This o

Finally, please pay attention to my column and make good friends with YK bacteria