当前位置:网站首页>Written interview topic: judge whether there is a link in the list

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

2020-11-08 10:30:33 http://www.ubytovani-jihlava.cz

        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 :

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {

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

    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 .

版权声明
本文为[http://www.ubytovani-jihlava.cz]所创,转载请带上原文链接,感谢