“This is the 11th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021.”

Topic describes

Give you the head node of a linked list and check if there are rings in the list.

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

The original title

Map thinking analysis (hash table thinking)

The first way of thinking about this problem can be the Map method. The analysis is as follows:

If we want to determine if a linked list has rings, we can create a structure of type map

Put in each of the linked list nodes

Iterate to the end

If the list ends, then the list is not a circular list

Duplicate entries appear in the linked list, which is a circular list

If the heade is null or there is only one node, return false;

The Map code

var hasCycle = function (head) {
    if(! head || ! head.next)return false;

    const mapper = new Map(a);let currentNode = head.next;

    while (currentNode) {
        if (mapper.has(currentNode)) {
            return true;
        } else {
            mapper.set(currentNode, currentNode);
        }
        currentNode = currentNode.next;
    }

    return false;
};
Copy the code

Complexity analysis

Time complexity: O(N)O(N), where NN is the number of nodes in the linked list. In the worst case we need to traverse each node once.

Space complexity: O(N)O(N), where NN is the number of nodes in the linked list. Mostly hash table overhead, in the worst case we need to insert each node into the hash table once.

Fast and slow node thinking analysis

A fast or slow pointer, as its name implies, first requires two Pointers, one fast and one slow

The slow pointer points to the first variable, the fast pointer points to the next, and moves backwards each time, taking one step at a time, and two steps at a time.

If the list has a ring, then the fast and slow Pointers must meet.

If the fast and slow Pointers meet, the linked list has a loop

If the fast pointer ends, the list is acyclic

Boundary value analysis is the same as Map.

Graphic analysis

Fast and slow pointer code implementation

var hasCycle = function (head) {
    if(! head || ! head.next)return false;
    let preNode = head;
    let nextNode = head.next;
    while(preNode ! == nextNode) {if(! nextNode || ! nextNode.next)return false;
        preNode = preNode.next;
        nextNode = nextNode.next.next;
    }

    return true;
};
Copy the code

Complexity analysis

Time complexity: O(N)O(N), where NN is the number of nodes in the linked list.

When there are no rings in the list, the fast pointer will arrive at the end of the list before the slow pointer, and each node in the list will be accessed at most twice.

When there are loops in the list, the distance between the fast and slow hands decreases by one after each turn. The initial distance is the length of the ring, so at most NN rounds are moved.

Space complexity: O(1)O(1). We only used the extra space of two Pointers.