LeetCode algorithm learning – list – ring list II

Hello, everyone. Today, I would like to share with you the next LeetCode intermediate difficulty topic, Circular Linked list II

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, return the first node where the list started to enter the loop. Null is returned if the list is loopless.

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 that pos is only used to identify the ring case and is not passed as an argument to the function.

Note: Modifications to the given list are not allowed.

Advanced:

Can you use O(1) space to solve this problem?

Example 1 input: head = [3,2,0,-4], pos = 1 output: return list node with index 1 explanation: there is a loop in the list with a tail connected to a second node. Example 2 input: head = [1,2], pos = 0 output: return a linked list node with index 0 description: there is a loop in the list with a tail connected to the first node.Copy the code

Analysis of the

Ontology is the continuation of the circular linked list of the advanced problem, the key point is how to judge the first point into the ring

There are 2 solutions

1. The Map method

2. The pointer method

Solution a:The Map method

Train of thought1.I'm recording all the nodes that pass by2.Since the map is recorded backwards, if there is a visited node, it must be the first node in the loop */var detectCycle = function (head) {
  // First exclude special conditions such as [] or [1]
  if (head === null || head.next === null) {
    return null;
  }

  let map = new Map(a);let cur = head;
  while(cur ! = =null) {
    // If it exists, it must be the first node
    if (map.get(cur)) {
      return map.get(cur);
    }

    // Record each node from front to back
    map.set(cur, cur);
    cur = cur.next;
  }

  return null;
};
/* Complexity time O(n) space O(n) */
Copy the code

Method 2:Double pointer method

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

The idea is that the distance from the beginning to the entrance is I and the distance from the entrance to the point where the fast and slow Pointers overlap is J and then you take k steps back to the point where the fast and slow Pointers overlap so if you take j plus k from any point in the ring, you will return to the origin1.First, the fast pointer (f) must take twice as many steps as the slow pointer (s)2.When the fast pointer f coincides with s1.The distance traveled by the fast pointer is f=a+n(b+c)+b;2.The distance traveled by the slow pointer is s= A +k(b+c)+b;3.Because the fast pointer is the distance of the slow pointer2So we get 2a plus 2k times b plus c plus 2b is equal to a plus n times b plus c plusb= >  a=-(2k-n+1)(b+c)+c
    4.From the above equation, we can know that the starting point of step A === s is the point of step C from the coincidence point, but A and C are unknown, so we can use the coincidence collision method to get the entry point5.Put a pointer in the head, and walk at the same time as s. When they meet, they arrive at the loop's entry point */var detectCycle = function (head) {
  // First exclude special conditions [] [1]
  if (head === null || head.next === null) {
    return null;
  }

  let f = head;
  let s = head;
  while(f ! = =null&& f.next ! = =null) {
    f = f.next.next; // The fast pointer takes 2 steps at a time
    s = s.next; // The slow pointer moves one step at a time

    // If they meet, there is a ring
    if (f === s) {
      // Set a pointer to the header
      let extra = head;
      // When a superposition collision occurs, the entry point of the loop is reached
      while(extra ! == s) {// Step by step from the beginning
        extra = extra.next;
        // S from the overlap point also step by step
        s = s.next;
      }
      returns; }}return null;
};

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

conclusion

This is a medium difficulty problem, the Hash is easy to understand, but the double pointer requires a lot of derivation.

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!