The list

The data structure

  • It can be divided into four types according to the storage structure

    • Sequential storage
      • The storage space must be continuous
      • Put them in logical order
    • Chain store
      • Linear structure
      • Nonlinear structure
    • Indexes are stored
    • Hash stored

  • According to the context between the elements divided into two

    • Linear structure: a non-empty data structure with one and only root node and at most one direct precursor and one direct successor per node

    • Nonlinear structure: Data structures that do not satisfy linear structure

The list

  • A linked list is used to store an ordered collection of elements. Unlike an array, the elements in a linked list are not stored in contiguous storage space. Each element consists of a node that stores the element itself and a pointer to the next element. When you want to move or delete an element, you just need to change the pointer on the corresponding element. Operation on linked list elements is more efficient than operation on array elements. Here is a schematic of the linked list data structure:

Circular linked list

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.

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

Example 3:

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

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.

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

answer

Fast and slow pointer solution
  • We define two Pointers: a slow pointer and a fast pointer. The slow pointer points to head and the fast pointer points to head
  • The fast pointer then moves forward two at a time and the slow one at a time to start traversing the list
    • Return false if head or head.next is empty
    • 2. Define two Pointers pre,cur and initialize both to head
    • 3. When cur is not empty and cur.next is not empty, pre moves backward one step at a time, and cur moves two
    • 4. If there are rings in the list, pre and cur will be equal. If there are no rings, false will be returned at the end
   var hasCycle = function(head) {
       if(! head || ! head.next )return false
       let pre = head,cur = head;
       while (cur&&cur.next) {
          pre = pre.next
          cur = cur.next.next
          if(pre === cur) {
              return true}}return false
   };
Copy the code
Json.stringify simplified implementation
  • Json.stringify will report an error if it has a loop
    var hasCycle = function(head) {
        try {
            JSON.stringify(head)
            return false
        } catch {
            return true}};Copy the code
  • Derive JSON ring checker
/** * loop checker */
function detectorCircular(obj) {
    var hasCircle = false.// Define a variable to indicate whether there is a ring
        cache = [];                   // Define an array to hold the property values of the object type

    (function(obj) {
        var keys = Object.keys(obj);              // Get an array of properties for the current object
        for (var i = 0; i < keys.length; i++) {
            var key = keys[i];
            var value = obj[key];
            if (typeof value == 'object'&& value ! = =null) {
                var index = cache.indexOf(value)
                if(index ! = = -1) {
                    hasCircle = true
                    break
                } else {
                    cache.push(value)
                    arguments.callee(value)
                    cache.pop()      // Note: The data is derived here, since the recursion returns, the following properties are not child properties of the data
                }
            }
        }
    })(obj)

    return hasCircle
}
/** ** json.stringify simplifies implementation *@param Obj The object * to be converted to a string@param IgnoreCircular Indicates whether to ignore "ring" checks */
  function stringify(obj,ignoreCircular) {
    if(! ignoreCircular && detectorCircular(obj)) {throw new TypeError('Converting circular structure to JSON')}const keys = Object.keys(obj)
    
    if(! keys.length) {return '{}'
    }
    
    const content = keys.map(key= > {
      const value = obj[key]
      
      if (typeof value === 'number') {
        return `"${key}":${value}`
      } else {
        return `"${key}":${stringify(value, true)}`
      }
    }).join(', ')
    
    return ` {${content}} `
  }
  const obj = {
    foo: {
      name: 'foo'
    },
    bar: {
      name: 'bar'.baz: {
        name: 'baz'.next: null // will point to obj.bar}}}; obj.bar.baz.next = obj.bar stringify(obj)Copy the code

The map method

  • Using map, all the way next through has… See if there’s duplication
    var hasCycle = function (head) {
        let dataMap = new Map(a)while (head) {
          if (dataMap.has(head)) {
            return true
          }
          dataMap.set(head, 1)
          head = head.next
        }
        return false
      };
Copy the code
Copy the code