Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

preface

Data structure and algorithm belong to the internal work of the developer, no matter how the front-end technology changes, how the framework updates, how the version iteration, it is the same content. Always remember in the byte youth training camp, moon shadow teacher said a word, do not ask front-end learning algorithm. Everyone in computer science needs to know about algorithms and has the subconscious to write high-quality code.

I. Problem description

Give you the head node of a linked list and check if 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, the metric system internally uses the integer POS to represent where the tail of the list is connected to in the list (the index starts at 0). Note: pos is not passed as an argument. Just to identify the reality of linked lists.

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

Example 1:

Enter: head = [3.2.0, -4], pos = 1Output:trueExplanation: A linked list has a ring whose tail is connected to a second node.Copy the code

Example 2:

Enter: head = [1.2], pos = 0Output:trueExplanation: A linked list has a ring whose tail is connected to the first node.Copy the code

Example 3:

Enter: head = [1], pos = -1Output:falseExplanation: There are no rings in the linked list.Copy the code

Tip:

  • The number of nodes in the list ranges from 0 to 104.
  • 105 <= Node.val <= 105
  • Pos is -1 or a valid index in a linked list.

Second, detailed explanation of ideas

Here are two main solutions

The first solution

  • Tags are used to mark the iterated nodes, and return true if a marked node is found
var hasCycle = function(head) {
    while(head){
        if(head.tag) return true
        head.tag = true
        head = head.next
    }
    return false
};
Copy the code

Second solution

  • Using the fast pointer, if there is a loop, the fast pointer takes two steps at a time, and the full pointer takes one step at a time. If there is a loop, the two Pointers must meet.
var hasCycle = function(head) {
    let slow = head, fast = head
    while(slow && (fast && fast.next)){
        slow = slow.next
        fast = fast.next.next
        if(slow==fast) return true
    }
    return false
};
Copy the code

subsequent

  • Address: circular linked list

Well, this force buckle – ring chain list ends here, I am Shao Xiaobai, a junior in the front end field, welcome to 👍 comments.