Shulou(Shulou.com)06/02 Report--

In this issue, the editor will bring you about how to judge whether the linked list has rings in leetcode. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

Why do you want to browse leetcode?

The data structure characterizes the format of data storage and the way data is manipulated. It is convenient for us big data developers to design better storage, reading and computing strategies. So in the java foundation, big data foundation, big data framework source code and so on all have a certain foundation, we should pursue to write more refined and efficient code.

Recently, in sorting out the java interview questions, we found that data structures and algorithms are used in many of our common tools, such as the underlying java, ordered set and other storage structures of redis, spark, mr and so on. So, if you want to thoroughly understand the underlying principles and write code with low time complexity, you still need to brush the data structure, and the data structure seems to be the threshold of the interview for bat data technology category. Of course, you'd better do platform development, and don't think you won't learn if you don't need it, it's just that you still suck.

Back to why do you want to brush leetcode?

Foreigners are all brushing, college students are also brushing, and they don't brush themselves. No matter how useful big data is, he is only developing at the bottom.

Here, you should spit blood.

As a result, today leetcode broke, and the first question was a question that I didn't understand before. The topics are as follows:

Given a linked list, determine if it has a cycle in it.

Is how to determine whether there is a ring in a linked list. Leetcode gives the following propositions and examples:

The first time I was asked this question in the interview when I graduated, and I looked confused. Who would do this if I didn't do the exercises?

Recently, there are three general ideas for careful consideration:

Exhaustive. Traversing from beginning to end, it points to null, which means there is no loop. This is obviously unreliable. Time complexity O (n)

Third-party storage. Store the pointer in hashset while traversing, and determine whether the current pointer exists in hashset, and if so, determine if there is a loop. Otherwise, there will be no ring. Time complexity O (n).

Public boolean hasCycle (ListNode head) {

Set nodesSeen = new HashSet ()

While (head! = null) {

If (nodesSeen.contains (head)) {

Return true

} else {

NodesSeen.add (head)

}

Head = head.next

}

Return false

}

Quick and slow pointer. The fast pointer takes two steps at a time, but the slow pointer takes one step. If there is no loop, the slow pointer can never catch up with the fast pointer, and the time complexity is O (n). If there is a ring, then the fast pointer will fall into the ring first, and the fast pointer will meet in a circle. The java code written on leetcode is as follows:

ListNode walker = head

ListNode runner = head

While (runnerrabbit null null runner.nextbread null) {

Walker = walker.next

Runner = runner.next.next

If (walker = = runner) {

Return true

}

}

Return false

The above is how to determine whether the linked list has a ring in the leetcode shared by the editor. If you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.