“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”

Circular linked lists

The title

Given a linked list, determine whether there are rings 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.

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.

Answer key

Ask questions

  • How do I prove that there are rings in a linked list?

Analysis of the

  • When there is a node in the linked list, it can be traced continuouslynextThe pointer arrives again, proving the existence of a ring in the list.

solution

  • Pass each node through the linked listsetWay toMapIn the object.
  • setBefore you go throughhasWay to determineMapObject whether the node exists, if so, the ring;
  • When the traversal is complete, that isnextPointer tonullIf, it is acyclic.

Code implementation

/ * * *@param {ListNode} head
 * @return {boolean}* /
var hasCycle = function(head) {
  let pointer = head;
  let map = new Map(a);while(pointer ! = =null) {
    if (map.has(pointer)) {
      return true; 
    } else{ map.set(pointer); pointer = pointer.next; }}return false; 
};

Copy the code

Spatial complexity

Because the space occupied by the Map object in the above code is affected by the linked list, the space complexity is O(N).

Spatial complexity

The time complexity of traversing the list through while in the above code is O(N) affected by the length of the list.

The advanced

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

Ask questions

  • How do I prove that a linked list has a ring by not storing a linked list node?

Analysis of the

  • Can be through the fast and slow pointer (fast pointer every two steps, slow pointer every step);
  • Passes if the next digit of the fast pointer still has a valuewhileContinue to move the speed pointer;
  • If fast and slow Pointers meet (overlap), the linked list is looped, and returns True.
  • If the fast pointer reaches the end of the list and still does not encounter the slow pointer, the list is looped and False is returned.

Code implementation

/ * * *@param {ListNode} head
 * @return {boolean}* /
 var hasCycle = function(head) {
    let fast = head;
    let slow = head;
    while(fast&&slow&&fast.next){
        fast = fast.next.next;
        slow = slow.next;
        if(slow == fast)return true

    }
    return false;
};
Copy the code

Interesting experiment

Analysis of the

  • Traversing a linked list with a loop will continue forever.
  • Converting a dead-loop linked list object to a JSON string raises an error

No chain table

Have a chain table

Through the above experiments, we can prove that the conversion of a linked list with rings to JSON objects will report errors

  • Can be achieved bytry catchTo catch errors to see if there is a ring

Code implementation

/ * * *@param {ListNode} head
 * @return {boolean}* /
var hasCycle = function(head) {
  try {
    JSON.stringify(head);
    return false;
  } catch (err) {
    return true; }};Copy the code