“This is the 16th day of my participation in the August More Text Challenge.

If there are rings in the linked list, please find the entry node of the ring, otherwise, output NULL.

Train of thought code

// 1, fast and slow pointer Floyd algorithm
// a, find the meeting point b, find the entrance
function EntryNodeOfLoop(pHead) {
    var fast = pHead;
    var slow = pHead;
    if(pHead === null || pHead.next === null)
    return null;
    // The speed of the fast pointer is twice that of the slow pointer
    while(fast ! = =null&& fast.next ! = =null) {
        if(fast.next.next === slow.next)
            break
            // The two nodes meet
        
        
    }
    // Now the speed is the same, but the pointer is still in the encounter position, and the distance from the head node to the entry node is equal to
    // The distance from the encounter node to the entry node, at this time, the same speed forward will meet at the entry node
    fast = pHead;
    while(fast ! == slow){ slow = slow.next; fast = fast.next; }return slow;

}
Copy the code