# List the entrance of the central node | punch brush

Posted on Oct. 28, 2023, 9:46 a.m. by Annette Holland
Category: The front end Tag: algorithm

## Topic describes

Given a linked list, find the entry node of the linked list's ring if it contains rings, otherwise, null.

## Thought analysis

Declare two Pointers P1, P2

• 1. Check whether the linked list has rings: P1, P2 start from the head, P1 take two steps, P2 take one step, if they can meet, then there are rings

• 2. Start counting from a node in the ring and return to this node to get the length of the linked list ring

• 3.P1 and P2 return to the head node and let P1 go the length step first. When P2 and P1 meet, it is the starting point of the linked list ring

## AC code

``````class nodeList {
constructor(val) {
this.val = val;
this.next = null; }}/* 1. Check whether the list has rings: P1, P2 start from the head, P1 take two steps, P2 take one step, if they can meet, then there are rings 2. P1, P2 go back to the head node and let P1 go the length step first. When P2 and P1 meet, it is the starting point of the linked ring */
}
//1. Check whether there is a ring
while(p1 ! = p2) {if (p2 === null || p2.next === null) {
return null;
}
p1 = p1.next;
p2 = p2.next.next;

}
//2. Get the length of the ring
let temp = p1;
let length = 1 ;
p1 = p1.next;
while(temp ! = p1) { p1 = p1.next; length++ }//3. Find the public node
while (length  0) {
p2 = p2.next;
length--;
}
while(p1 ! = p2) { p1 = p1.next; p2 = p2.next; }return p1;
}

let node1 = new nodeList(1);
let node2 = new nodeList(2);
let node3 = new nodeList(3);
let node4 = new nodeList(4);
let node5 = new nodeList(5);
let node6 = new nodeList(6);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node3;
console.log(EntryNodeOfLoop(node1));
Copy the code``````

## conclusion

The first pointer p1 points to head, and the second pointer P2 points to head.next. Then the loop starts every time the first pointer takes one step forward and the second pointer takes two steps forward. If P1 is equal to p2, that means there's a loop in the list, out of the loop.

I want to find the length of the loop, which is the loop, and when the pointer cur is equal to p1 again, I get the length of the loop

The third step is to find the entry node, so that P1 and P2 will all come to head again, and P2 will go the length step first, then P1 and P2 will go forward together, and the node where P1 === P2 is the entry node.