Topic link

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

Title introduction

Given a linked list, return the first node where the list begins to loop. This returns NULL if the list is acyclic. If there is a node in the list that can be reached again by tracing the next pointer, then there is a ring in the list. To represent the rings in a given list, use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there is no loop in this list. Linked lists are not allowed to be modified

The sample

Input: head = [3,2,0,-4], pos = 1 output: returns the list node with index 1.Copy the code

Input: head = [1,2], pos = 0 output: returns a list node with index 0.Copy the code

Input: head = [1], pos = -1 Output: returns NULL Explanation: There are no loops in the linked list.Copy the code

Their thinking

1, 2, subject using the way of how Pointers slow pointer every step forward, quick hands every time I take two steps forward, if how Pointers can meet the certificate chain table 3, if the list has a ring with a loop, and how quickly a pointer, when they met, meet at this time the location of the distance into the ring and head node to point into the ring distance is the same. 4. Return one pointer to the head node and move forward with the other pointer one step at a time. The encounter point is the first node in the loop

Code implementation

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

/ * * *@param {ListNode} head
 * @return {ListNode}* /
 var detectCycle = function(head) {
     if(! head)return null;
     let p = head;  / / pointer to slow
     let q = head;  / / pointer
     // Check whether there is only one node, only one node has no ring, and execute error, do not ask me how to know!!
     if(! q.next)return null;
     // Loop conditions: p and q are not equal, and fast pointer next is not null
     // If p and q are equal, the current position is the encounter point
     do{
         p = p.next;
         q = q.next.next;
     }while(p ! == q && q && q.next);// If next is null, then there is no loop
     if(! q || ! q.next)return null;
     // return p back to the head node
     p = head;
     // Each time the two Pointers take a step forward, they meet at the entry point
     while( p! == q){ p = p.next; q = q.next; }// if p and q want to wait, return either one
     return q;
 }
Copy the code