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 */
function EntryNodeOfLoop(head) {
    if(! head || ! head.next) {return null
    }
    let p1 = head;
    let p2 = head.next;
    //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
    p1 = p2 = head;
    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.

This article is participating in the “Digging Gold 2021 Spring Recruitment Campaign”, click to view [activity details](