Basic knowledge of

  1. So let’s review the concept of linked lists
    • Simply put, a linked list node stores data for the current node and an address reference to the next node.

  1. Circular linked list

The title repeat

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:Copy the code

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. Source: LeetCode Link: https://leetcode-cn.com/problems/linked-list-cycle Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Their thinking

1. The hash table

  • The whole list is traversed, and the reference of the whole node is taken as the key and hashed. In the traversal process, if the same reference already exists in the table, it is judged to have a ring.
  • Note: When implementing js, do not use Object as a hash table. Because the object key must be a string or symbol, js will use stringify as the key, resulting in errors.
  • Time complexity: In the worst case, this method needs to traverse the entire list, so the time complexity is O(N), where N is the number of nodes in the list.
  • Spatial complexity: This method requires an entire map to assist, so the spatial complexity is also O(N), where N is the number of nodes in the linked list.
  • Implementation code:
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {boolean} */ var hasCycle = function(head) { if (! head || ! head.next) { return false } const hashMap = new Map() let has = false function getAllList(head) { if (! has) { if (hashMap.get(head)) { has = true } else { hashMap.set(head, head) if (head.next) { getAllList(head.next) } } } } getAllList(head) return has };Copy the code

2. Fast and slow pointer

  • Create two Pointers, one taking 1 step and one taking 2 steps, if there is a ring, then they must meet.
  • Time complexity (N is the number of nodes in the linked list) :
    • In the acyclic case, the time required is N/2, and the fast node will reach the node quickly
    • In the case of a ring, assuming that the length of the ring is a, the length of the ring is n-a, and the total number of steps is S, a + S * 1 = A + S * 2 – (n-a), s = N + A is obtained. In the worst case, that is, when the length of the ring is equal to the length of the node, the time required is N * 2, so the time complexity is O(N).
  • Space complexity: only two new Pointers, O(1)
  • Implementation code:
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; Var hasCycle = function(head) {if (! head || ! head.next) { return false } let has = false let slow = head let quick = head while(slow.next && quick.next && quick.next.next && ! has) { slow = slow.next quick = quick.next.next if (slow === quick) { has = true } } return has };Copy the code