The topic of dry

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:

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

Solution: Double pointer

Ring instructions are included in the list when we list a node into a loop, the node is not certain, but we can define the two Pointers, tandem, fast after the pointer to the two nodes, if there is a ring, so fast pointer will generally in the second round of catch up with the first round of the pointer, so they will be in a certain period of time overlap; If there is no loop, point to the tail node until the end exits, returning false

Code:

Execution time: 84 ms, beating 95.11% of users in all JavaScript commits

Memory consumption: 39.9 MB, beating 97.09% of all JavaScript commits

var hasCycle = function (head) {
    // First check if the list has a value or only one value returns false
    if (head == null || head.next == null) return false
    let index1 = head;
    let index2 = head.next;
    // The third judgment is in case we have only two elements and no rings, then we get an error at Next
    while(index1 ! =null&& index2 ! =null&&index2.next! =null) {
        index1 = index1.next
        index2 = index2.next.next
        if (index2 == index1) {
            return true}}return false
};
Copy the code