Recently I have been looking at data structures and algorithms, trying to sum up my debut ~

TL; DR

Circular list, every step, see if it’s labeled, it’s definitely a ring, and it starts here. If there is no sign, continue to go ~

Exercise: Determine if there are rings in a linked list

Judging whether there are rings in the list is actually a bit like wandering around. How do you know that you have gone through a circle? In fact, as long as you come to the same place the second time, you have gone through a circle.

So, every time you pass a place, you put a mark on that place, and if you see that mark again, that place has swam, which means that you have walked in a circle.

var hasCycle = function (list) {
  let p = list
  while(p){
    // There is a circle
    if(p.flag) return true
    // If you encounter those you haven't walked on, mark them and continue walking
    p.flag = true
    p = p.next
    
  }
  return false
};
Copy the code

You can look at other solutions to the official problem, and you can focus on the speed pointer

Practice: Where does the ring start

You can follow the idea above, but I don’t think it’s much

var detectCycle = function (list) {
  let p = list;
  while (p) {
    if (p.flag) return p
    p.flag = true
    p = p.next
  }
  return null;
};
Copy the code

Other official solutions can focus on the speed pointer

reference

  • The front-end algorithm and data structure of xiuyan