1. Find the starting point of the circular list

Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless. — From force link #### ring linked list II

Check if it’s a circular list

1.2 Use of fast and slow Pointers

Let’s assume that student A has to take A step to get to the starting point, and student B has taken 2a+1 step away from the starting point. Suppose student A walks to the position x and meets student B, then x-A = 2(x-1) + 1; X is equal to a-1, which means that if you go to the place where you meet you have to take a-1 steps, and you’re a+1 steps away from the starting point.

After meeting, let student B move forward one more step, so it is a step away from the starting point A, and then put student A in front of the first grid, student A is also a step away from the starting point, and then student A and student B take a step forward each time, and the place where they meet is the starting point of the ring.

The code implementation is as follows:

 function ListNode(val) {
     this.val = val;
     this.next = null;
 }

/ * * *@param {ListNode} head
 * @return {ListNode}* /
var detectCycle = function(head) {
    if(! head)return null;
    if(! head.next)return null;
    if(! head.next.next)return null;
    let p = head;
    let q = head.next.next
    while(q && q.next && q ! == p) { p = p.next; q = q.next.next; }if(! q || ! q.next) {return null;
    }
    q = q.next.next;
    p = head;
    while(q ! == p) { q = q.next; p = p.next; }return q;
};
Copy the code

1.2 Use array and Set implementation

All the linked list nodes are stored in an array or a Set, and the first repeated node is the starting point. The list is traversed, and then the array or Set is checked to see if the same node exists. If so, the current node is returned.

The code implementation is as follows

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

/ * * *@param {ListNode} head
 * @return {ListNode}* /
var detectCycle = function(head) {
    const set = new Set(a);let curNode = head;
    while(curNode) {
        if (set.has(curNode)) {
            return curNode;
        }
        set.add(curNode);
        curNode = curNode.next;
    }
    return null;
};
Copy the code