Nuggets team number online, help you Offer impromptu! Click for details

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.

Example:

Their thinking

There are two approaches to this problem:

  1. Use the newly created array
  • Create an empty array res
  • Traverses the list to determine whether the node currently traversed exists in the new array RES. If it does not, the node will be stored in the new object. If it does, it indicates that the list has a ring
  1. Linked list: Fast and slow Pointers
  • This idea involves the catch-up problem of primary school learning, and two Pointers need to be defined, one fast pointer and one slow pointer
  • If the list has a ring, the fast pointer must meet the slow pointer in the ring, as shown

The problem solving code

Array judgment:

var hasCycle = function (head) {
    if(! head)return false;
    const res = [];
    while (head) {
        if (res.includes(head)) {
            return true;
        }
        res.push(head);
        head = head.next;
    }
    return false;
};
Copy the code

Link list fast or slow pointer judgment:

var hasCycle = function (head) {
    if(! head)return false; 
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            return true; }}return false;
};
Copy the code

conclusion

A thousand miles, not small streams into rivers, today is the first day to brush algorithm, I hope to stick to it in the future