The title

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.

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

Fast and slow pointer

Give head node specifies how Pointers, when meet, how Pointers that met the head pointer and a pointer to the first node of the annular node distance is equal (elementary school mathematics), at this point, the pointer to the head node will be slower, and faster pointer synchronous walk together in the same steps, when they met the first node node is the ring

leetCode

var detectCycle = function(head) {
    // If there are no nodes or the length of the node is 1, null is returned
    if (head === null || head.next === null) {
        return null;
    }

    var p1  = head;
    var p2 = head;
    // The fast and slow nodes start to walk
    while(p2 ! = =null&& p2.next ! = =null) {
        p1 = p1.next;
        p2 = p2.next.next;
        // Break out of the loop when they meet
        if (p1 === p2) {
            break; }}// If the fast and slow nodes are not equal, it is not a circular list
    if(p1 ! == p2) {return null;
    }

    var p1 = head;
    // The first node of the ring.
    while(p1 ! == p2) { p1 = p1.next; p2 = p2.next; }return p2;
};
Copy the code