LeetCode algorithm learning — linked list – ring linked list

Hello everyone today to share the next LeetCode easy difficulty of the title [circular linked list](leetcode-cn.com/problems/3s…)

Here is mainly to share ideas and comments, for you to better understand the problem solution, the code part is to refer to LeetCode translated into javascript code,

The title

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 continuously tracing the next pointer, there is a loop in the list. To represent the loop in a given list, we use the integer POS to represent where the end of the list is joined into the list (the index starts at 0). If pos is -1, there are no rings in the list. Note: POS is not passed as a parameter, only to identify the actual condition of the linked list.

Returns true if there is a loop in the list. Otherwise, return false

Advanced:

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

Input: head = [3,2,0,-4], pos = 1 output: trueCopy the code

Analysis of the

/ * analysis

1. If there is a ring, it must have been accessed

2. How to find a way to prove whether this point has been visited

solution

1. Fast and slow pointer

2. The set method

Solution a:How fast a pointer

Train of thought1.The fast pointer goes at once2Step, slow pointer one step at a time,2.If there is a ring, there must be a ring3.If the node. Next tonull, indicating the end of the access ends the loop */var hasCycle = function (head) {
  // Order special conditions such as; [], [1]
  if (head === null || head.next === null) {
    return false;
  }

  let node1 = head; / / pointer to slow
  let node2 = head; / / pointer

  // If the fast pointer is null or the next of the fast pointer is null,
  // End the loop
  while(node2 ! = =null&& node2.next ! = =null) {
    // The slow pointer moves one step at a time
    node1 = node1.next;
    // The fast pointer takes two steps at a time
    node2 = node2.next.next;
    // = = = = = = = = =
    if (node1 === node2) {
      return true; }}return false;
};

/* Complexity time O(n) space O(1) */
Copy the code

Method 2:The Set method

(This question is a reference to the official website of the problem solution, because at that time considering the advanced problem time complexity O(1), so we ignored this simple straightforward method)

Code reference leetcode-cn.com/problems/li…

Train of thought1.Record visits2.If the node */var hasCycle = function (head) {
  // Use set to record the nodes visited
  const set = new Set(a);let cur = head;

  // When cur === NULL, it indicates the end of the list
  while(cur ! = =null) {
    // Check whether it has been accessed
    if (set.has(cur)) {
      return true;
    }
    set.add(cur);
    cur = cur.next;
  }

  return false;
};

/* Complexity time O(n) space O(1) */
Copy the code

conclusion

This is a simple question to examine how to prove that “nodes” have been accessed.

You can look at a column I share (front-end algorithm) there are more questions about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me a like, thank you very much

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Part of the material in this article comes from the network. If there is infringement, please contact delete, [email protected]

Yesterday, I supported Hongxing Erke and Michelle Ice City. Today, I supported Huiyuan Juice. Ha, ha, ha, ha. Come on, Zhengzhou! Henan come on! Go China!