Force button topic link

The question:

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

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). 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.

Linked lists are not allowed to be modified.

Train of thought (B station JS Old Bi) :

  • Does it have a ring?
    • Define a fast pointer fast and a slow pointer. Starting from the head node, the fast pointer moves two nodes at a time, and the slow pointer moves one node at a time. If the list is loopless, the fast pointer points to null first. If the list has rings, fast and Slow must meet on the way
    • If there is a loop: the fast pointer takes two steps at a time, and the slow pointer takes one step at a time. As they both enter the loop, we assume that the FAST pointer is behind the slow pointer, so every operation we make will make the FAST pointer catch up with the slow pointer, which means fast is one step closer to the slow pointer.
    • At how many steps do the fast and slow hands meet? They start a few steps apart as they enter the ring, so the fast pointer takes a few steps to catch up with the slow pointer
  • If there is a ring, how do you find the entrance to the ring?
    • The slow pointer goes one step slowly, and the fast pointer goes two steps fast until the moment when the slow pointer enters the ring, to see how many steps the slow pointer differs from the fast pointer. The fast hand must travel twice as far as the slow hand. If the slow pointer took 3 steps, the fast pointer must have taken 6 steps.
    • See when they meet? The fast pointer moves one step more than the slow pointer each time. That is, the fast pointer moves one step in the direction of the slow pointer each time. At this time, the fast pointer is several steps behind the slow pointer, so it needs several steps to catch up with the slow pointer
    • When the fast and slow Pointers meet, place the fast Pointers at the beginning of the linked list, and both the fast and slow Pointers move one step at a time

  • When the slow pointer reaches the entry point, the distance traveled by the fast pointer is 2L. If the whole length of the ring is set as D, the remaining distance is (d-L), that is, the number of steps that the fast pointer needs to catch up with the slow pointer. Then the slow hands take (D-L) steps, and the fast and slow hands meet
  • After the encounter, the fast pointer is placed at the beginning, and the slow pointer continues in the ring and the encounter point begins to move forward. So how many steps does the slow pointer need to take to reach the starting position of the ring? D minus d minus L is l steps

  • If (L >d), that is, the ring is short and the slow pointer has not reached the entrance of the ring, while the fast pointer has completed the ring and has cycled n times in the ring and stopped at a certain position. But we don’t really care how many times the fast pointer goes around the ring, we just care what node it ends up at in the ring
  • The distance between the fast pointer and the slow pointer is r,l=nd+r
  • How many steps does the fast pointer need to take to catch up with the slow pointer? (d-r) step, then meet, put the fast pointer to the head node, the slow pointer continues to move forward in the ring. The fast pointer takes l steps from the beginning node to the entrance of the ring. However, the slow pointer moves (D -(d-R)) = R to the entrance of the ring. At this time, it is not guaranteed that the fast and slow Pointers meet, and the fast pointer may not finish (because L >d, L is long), so the slow pointer may circle n times in the ring, that is, the distance of the slow pointer is (r+nd) = L. So the speed is the same as the slow, and then they meet at the entrance of the ring, and they go back to this node

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

/ * * *@param {ListNode} head
 * @return {ListNode}* /
var detectCycle = function(head) {
    if (head === null) {// If the list is empty, return empty
        return null
    }
    let fast = head
    let slow = head
    let isCycle = false
    
    // Check whether the list has rings
    while(fast.next! =null&& fast.next.next! =null){
        slow = slow.next
        fast = fast.next.next
        if(slow===fast){
            isCycle = true
            break}}// If the list is non-cyclic, Null is returned
    if(! isCycle){return null
    }
   // If the list has a loop, place the fast pointer at the beginning of the list when the fast and slow Pointers meet for the first time
    fast = head
    while(slow! ==fast){ slow = slow.next fast = fast.next }return fast
};
Copy the code