Topic describes

LeetCode 141 circular linked list

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?

 

Example 1:

Input: head = [3,2,0,-4], pos = 1 output: true explanation: there is a ring in the linked list whose tail is connected to a second node. 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. Example 3:

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

Tip:

The number of nodes in the list ranges from [0, 104] -105 <= node. val <= 105 pos is -1 or a valid index in the list.

Thought analysis

First of all, when a linked list has a ring, one of the things that always happens is that when you access a node, you discover that node has been accessed before.

So, if you want to make this judgment, the intuitive idea is to record every node that you’ve visited before. You can use a data structure like Set (based on a hash table that stores only non-repeating elements). If the node cannot be added to a Set, it already exists in the Set, which is a ring. This method requires additional storage space, O(n) in the worst case, so the space complexity and time complexity are O(n).

The second solution, which involves a ring scenario, can be likened to a chase between two people on a circular track. From the same starting point, person A starts at 1 meter per second, and person B starts at 2 meters per second. So on this circular track, two people will eventually meet. Let’s say the track is 10 meters long, so when B catches up with A again, 10 seconds have passed, so A has completed one lap, B has completed two laps, and they meet. Therefore, the time complexity of this method is O(n), the space complexity is constant, and only the distance run by two people is recorded as O(1).

AC code

Here is only the code for solution 2:

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: ListNode) -> bool: # boundary case [] if head == None or head. Next == None: Slow = head # step 1 fast = head # step 2 while (slow! = None and slow.next ! = None and fast ! = None and fast.next ! = None and fast.next.next ! Next if (slow == fast): return True return False #Copy the code

conclusion

Simple problem, need to pay attention to some boundary use cases, and nullation treatment. If the interview encounters this kind of topic mainly is inspects the code realization ability, and the language control ability. Because the idea is not difficult, basic can say. So the focus is on coding implementation. No one knows how to write code.

Author: kirinzer

Links: juejin. Cn/post / 693450…

Source: Nuggets

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.