First, understand the topic

141. Circular lists

Given a linked list, determine whether there are rings in the list.

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, we use the integer pos to represent where in the list the tail joins (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.

Returns true if there are rings in the list. Otherwise, return false.

Example:

Head = [3,2,0,-4], pos = 1trueExplanation: A linked list has a ring whose tail is connected to a second node.Copy the code

Ii. Solution analysis

(1) How to solve the problem

  • Two people in the circular playground starting at the same time, the speed of the fast person will overtake the slow person one lap;
  • Use a fast pointer and a slow pointer to traverse the linked list. If the Pointers can meet, the linked list has a circle.

(2) Steps to solve the problem

  • withOne fast, one slow, two handsIterate over the linked list, returning if Pointers can meettrue 。
  • After traversal, return without meetingfalse 。

Three, code implementation

Based on the above solution, we will use JS to implement this problem. The specific implementation code is as follows:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var hasCycle = function(head) {
    // 1. Define a p1 pointer to the header
    let p1 = head;
    // 2. Define a p2 pointer to the header
    let p2 = head;
    // 3. Suppose P1 is the slow value and P2 is the fast value
    // 3. Therefore, only P2 has a next node, which means that p1 following it also has a next node
    while(p1 && p2 && p2.next){
        // p1 walk around
        p1 = p1.next;
        // 3.2 P2 go two laps
        p2 = p2.next.next;
        // 3.3 If P1 and P2 are equal, then they meet, indicating that there is a ring; Return true
        if(p1 === p2){
            return true; }}// 4. Otherwise return false
    return false;
};
Copy the code

The above is about the circular linked list of problems, DO not know whether it is helpful to small friends?

We’ll see you next time at 👋👋👋