# Written interview topic: judge whether there is a link in the list

2020-11-08 10:30:33

Original published in ：

Before that U In the company's written examination , Come across such a problem ：

Judge whether a single chain table has rings .

First of all, let's look at this common sense ： The loop in reality and the loop of single linked list , What's the difference ？

obviously ： The loop in reality , There can be two directions , Either cycle , Or escape . However , In a single chain table , The pointer next There can only be one point , So the loop list must loop forever , There is no exit . As shown in the figure below ：

Back to the question itself , How to judge whether a single linked list has a ring ？

### Algorithm 1： Tagging

The easiest thing to think of must be the notation . When traversing the linked list , Record the visited nodes . If it's a circular single chain list , Then there must be repeated visits to nodes . This kind of thinking is very natural .

When marking , Consider using hash map perhaps hash set, It takes some space . Because the idea is clear , So there's no need to introduce the program in detail .

### Algorithm 2： The brute force algorithm

violence , It's also a way to solve problems , Although not necessarily the best way .

Think about it this way ： All the way to the dark , If we get to the end , There is no ring , If you don't get to the end , It means that you keep circling in the ring .

I was just leetcode I did this topic on , The law of violence , Can pass all test cases , The code is as follows ：

``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/

count := 0
max := 12000
for ; head != nil && count < max; {
count++
}

if count == max {
return true
}

return false
}``````

It's easy to see , There are limitations to this brute force algorithm ： such as , If the list is long enough , It can also lead to count and max equal , It may be misjudged .

### Algorithm 3： Speed pointer

The motorcycle is in the back , Bicycles are in front , Motorcycles catch up with bicycles , If it's a circular road with no way out , Then the motorcycle will catch up with the bicycle .

therefore , We can take a similar approach , Keep the fast pointer behind , Slow pointer ahead , We can judge whether a single linked list has a ring . The advantage of this method is , The space complexity is O(1), And there will be no miscalculation .

Now that you know the idea , Writing programs is a very simple thing , So I won't go back to .

Have a nice weekend , We'll talk about it next week , Be there or be square .