Topic describes

Given a linked list, determine whether there are rings in the list.

If there is a node in the list that can be reached again by following the next pointer continuously, then there is a ring in the list. To represent the rings in a given list, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there are no rings in the linked list. Note: POS is not passed as an argument, just to identify the actual state of the linked list.

Returns true if there are rings in the list. Otherwise, return false.

Advanced: Can you solve this problem with O(1) (i.e., constant) memory?

The sample

Example 1:

Input: head = [1,2], pos = 0 output: true explanation: there is a ring in the linked list whose tail is connected to the first node.Copy the code

Example 2:

Input: head = [1,2], pos = 0 output: true explanation: there is a ring in the linked list whose tail is connected to the first node.Copy the code

Example 3:

Input: head = [1], pos = -1 Output: false Explanation: There are no loops in the linked list.Copy the code

Their thinking

Idea 1: Use hash tables

  • The hash table stores nodes that have been traversed. Each time a node is traversed, it looks for the existence of the node in the hash table. If it already exists, the linked list indicates the existence of a ring;
  • If the node does not exist in the hash table, the node is saved and traversal continues.
  • If the list is empty, return false

Idea 2: fast and slow pointer

  • Define two Pointers slow and fast. Starting from the same node, slow moves forward one step at a time and FAST moves forward two steps at a time, that is, fast is twice as fast as slow.
  • If there were a loop, slow and fast would definitely meet;
  • If there were no rings, then the two Pointers would not be equal;

AC code

Solution 1: Hash table

Var hasCycle = function(head) {let current = head let map = new map () while(current) { If (map.has(current)) return true if(map.set(current, true)) Next // continue through} return false // Node does not exist, return false};Copy the code

Solution 2: Fast and slow pointer

var hasCycle = function(head) { if(head == null) return false let slow = head let fast = head while(fast ! = null) {if(fast.next == null) {// Node does not exist, Next // The slow pointer moves one step backward fast = fast.next. Next // The fast pointer moves two steps backward if(fast == slow) {// The fast pointer encounters the slow pointer return true } } return false };Copy the code

Swipe questions and punch out records

This is the previous record of brush questions. If you are interested, you can take a look. If there are any bad places, I hope you can point out them. Or go to the comments section.

Leetcode15 history the most detailed answer key # 3 sum | punch brush

Leetcode215 | the first K’s largest element in an array clock in brush

conclusion

The process of writing questions is equivalent to a process of reflection, deepen their own impression. If you can write the solution in a way you understand, that’s enough. It doesn’t have to be much. People will grow.

Come on, HXDM! Aoli give!!

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign