The title

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). 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.

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

Solution idea 1: mark nodes

When traversing a node, mark the node. When the node traversed is marked, it indicates that there is a ring. Otherwise, it is a single linked list

leetCode:

/ * * *@param {ListNode} head
 * @return {boolean}* /
 var hasCycle = function(head) {
    var p = head;
    while (p) {
        if (p.next === null) {
            return false;
        }
        if (p.next.checked) {
            return true;
        }
        p.checked = true; // Indicates that the current node has been traversed
        p = p.next;
    }
    return false;
};
Copy the code

Solution idea 2: fast and slow pointer

Two Pointers are allocated to the head node. The first pointer takes one step at a time, and the second pointer takes two steps at a time. If the two nodes can meet, it indicates that there is a loop

leetCode:

/** * @param {ListNode} head * @return {boolean} */ var hasCycle = function(head) { var p1 = head; var p2 = head; while (p2 ! == null && p2.next ! == null) { p1 = p1.next; p2 = p2.next.next; if (p1 === p2) { return true; } } return false; };Copy the code