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 fourth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Yesterday we did a circular list, today we’re going to do a circular list II

142. Circular linked List II

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

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 that pos is only used to identify the case of the ring and is not passed to the function as an argument.

Note: Modification of a given linked list is not allowed.

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

【 solution 1 】 Use Map

As in the previous problem, we use the Map solution directly, save the traversed node, and return the first traversed node

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

It can solve the problem, but the efficiency is still too low

【 solution 2 】 Fast and slow pointer

We use the second method, the fast and slow method, but the difficulty of this problem is not to determine whether there is a ring, but to find the first node in the ring.

We need to draw a picture here

Let’s say the slow pointer goes x nodes and meets the fast pointer, because the fast pointer goes twice as fast as the slow pointer, so the fast pointer goes 2x nodes

The node where the fast and slow Pointers meet is not necessarily the starting point of the ring, but it follows that there are x nodes in the ring

Let’s assume that the starting point of the ring is k nodes away from where the two Pointers meet. At this point, we can calculate that the distance from the beginning to the starting point is X-K, and the traversal from the encounter point to the starting point is also X-K.

At this point, we start over with a pointer, one step at a time. The slow pointer continues to traverse step by step. They’re going to meet at x minus k nodes, and that’s where the ring starts.

var detectCycle = function(head) {
    if(head === null) return null
    let slow = head
    let fast = head
    while(fast){
        if(fast.next===null) return null
        slow = slow.next
        fast = fast.next.next
        // The fast and slow Pointers meet
        if(slow === fast){
            let pre = head
            while(slow ! == pre){ pre = pre.next slow = slow.next }return pre
        }
    }
    return null
};
Copy the code

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