Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

This is the strength of the buckle series 5, today and friends together punch card buckle 141: the realization of circular linked list.

Topic describes

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.

Advanced:

Can you solve this problem with O(1) (i.e., constant) memory?

Example 1:

Input: head = [3,2,0,-4], pos = 1 output: true explanation: there is a ring in the linked list whose tail is connected to a second node.Copy the code

Example 2:

Input: head = [1,2], pos = 0 output: true explanation: there is a ring in the linked list whose tail is connected to the first node.Copy the code

Example 3:

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

Tip:

The number of nodes in the list ranges from [0, 104] -105 <= node. val <= 105 pos is -1 or a valid index in the list.

Source: LeetCode link: leetcode-cn.com/problems/li… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

This problem is to determine whether there are rings in the linked list, we can use the idea of fast and slow Pointers to solve, the so-called fast and slow Pointers, define a slow pointer to walk one step at a time, define a fast pointer to walk two steps at a time, so that if there are rings, they will always meet.

It’s like two people running together, one is slower, the other is faster, and they will meet at the same place on the track at some point

Code implementation

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
​
/ * * *@param {ListNode} head
 * @return {boolean}* /
var hasCycle = function (head) {
    if(! head)return false;
    let pre = head;
    let cur = head;
    while (cur && cur.next) {
        pre = pre.next;
        cur = cur.next.next;
        if (pre === cur) {
            return true; }}return false;
};
Copy the code

conclusion

The front end is long and long. We are all on the road. We hope to communicate with our friends and make progress together. Keep updating ing…..

Head over to the Leetcode column series to see more about unlocking.